找到一个分区，使得分区总和的最大值与最小值之差最小

Question

我正在解决一个算法研究的实践问题，并为下面的问题寻找最快的实现。

给定长度为N的正整数列表L，在L中定义A、B、C三个点，使列表分为三个分区。注意，A < B < C在索引方面。第一个分区是A和B之间的所有元素，第二个分区是B和C之间的所有元素，第三个分区是所有其他元素。

则设h,i,j为各分区的和。我想在所有可能的分区中找到max([h, i, j]) - min([h, i, j])的最小值。

例如，如果L = [4, 5, 6, 7, 6, 5, 4]，那么分割将是

a = [6, 7]
b = [6, 5]
c = [4, 5, 4] # reminder 
# because
h = sum(a) -> 13
i = sum(b) -> 11
j = sum(c) -> 13
# that minimize the difference
max([h, i, j]) - min([h, i, j]) -> 2

我目前想到的唯一方法是暴力强制所有可能的分区，以便

current_min = sum(L)
N = len(L)
for A in range(N):
for B in range(A, N):
for C in range(B, N):
sum_1 = sum(L[A:B])
sum_2 = sum(L[B:C])
sum_3 = sum(L[:A]) + sum(L[C:])
sums = [sum_1, sum_2, sum_3]
if max(sums) - min(sums) < current_min:
current_min = max(sums) - min(sums)

但是我可以看出我的解决方案并不理想。有更快的方法吗?

Answer 1

这里有一个方法，你可以计算总金额。计算总和的1/3。现在遍历列表并不断向sum1添加元素，直到它刚好超过总和的1/3(检查至少还剩下2个元素)。这是1个分区。同样地，继续把这个元素加到sum2里直到它刚好超过总和的1/3。剩余的元素构成分区3。

现在您可以以相反的顺序重复该过程，并查看max([h, i, j]) - min([h, i, j])的哪个集合给出最小值。

的想法是保持分区之间的差异总和尽可能小。这将自动确保总和的最大值和最小值之间的差最小。