我曾经遇到过类似的问题，但至今仍没有好的解决方法。这个问题是这样的：
给你一个长度为n（n<=1000）的正整数数组和一个正整数k（k<=n），k表示需要将该数组分割成k个连续子数组。你需要输出最小的m，其中m=max{s[1],...,s[k]}，s[i]表示第i个子数组的和。数组中的所有整数都在1到100之间。例如：
Input: Output:
5 3 >> n = 5 k = 3 3
2 1 1 2 3
将数组分成2+1 | 1+2 | 3可以最小化m。
我的暴力想法是让第一个子数组在位置i结束（对于所有可能的i），然后尝试以最佳方式将其余的数组分成k-1个子数组。然而，这是指数级的解决方案，永远不会奏效。
因此，我正在寻找好的解决方法。如果您有，请告诉我。
感谢您的帮助。
O(n log d)，其中d是输出答案。(一个上限是数组中所有元素的总和)。(或者在输出位的大小上O( n d ))。k，则当前的m是成功的（因此调整上限）。否则，您使用了太多的分区，并提高了m的下限。// binary search
binary_search ( array, N, k ) {
lower = max( array ), upper = sum( array )
while lower < upper {
mid = ( lower + upper ) / 2
// if the greedy is good
if partitions( array, mid ) <= k
upper = mid
else
lower = mid
}
}
partitions( array, m ) {
count = 0
running_sum = 0
for x in array {
if running_sum + x > m
running_sum = 0
count++
running_sum += x
}
if running_sum > 0
count++
return count
}
这个概念应该更容易理解。另外请注意，由于分区函数的单调性，如果您确定输出的d不太大，实际上可以跳过二分查找并进行线性搜索：
for i = 0 to infinity
if partitions( array, i ) <= k
return i
int best[k+1][n+1];
其中，best[i][j]代表将数组前j个元素划分为i个子数组所能获得的最佳结果。而best[1][j]仅仅表示前j个数组元素的总和。在已知第i行的情况下，可以按照以下方式计算第i+1行：
for(j = i+1; j <= n; ++j){
temp = min(best[i][i], arraysum[i+1 .. j]);
for(h = i+1; h < j; ++h){
if (min(best[i][h], arraysum[h+1 .. j]) < temp){
temp = min(best[i][h], arraysum[h+1 .. j]);
}
}
best[i+1][j] = temp;
}
best[m][n] 将包含解决方案。该算法的时间复杂度为O(n^2*k)，可能有更好的解决方案。
编辑：采用ChingPing、toto2、Coffee on Mars和rds的想法组合（按照当前页面上出现的顺序）。
设 A = ceiling(sum/k)。这是最小值的下界。通过任何一种提到的方法创建一个很好的分区，移动边框，直到找不到任何仍然可以减少最大子和的简单移动为止，以找到一个良好的最小上界B（如果它比下界大得多，你会发现通过移动边框可以轻易地得到改进）。
现在继续使用ChingPing的算法，知道上界值来减少可能的分支数量。这最后一阶段的时间复杂度为O((B-A)*n)，找到未知的B，但我认为比O(n^2)更好。
arraysum[a .. b] 将变为 cum[b] - cum[a-1]，但这并不意味着它是 O(n*k)，二次行为中的 n 来自于我们必须检查 j-i 可能的位置来找到最佳的子数组 best[i+1][j]。当然，可以通过简化来削减一些常数因子。 - Daniel Fischerbest[i+1][j]只在找到temp中的最小值后设定一次（实际上，我们可以消除temp，这可能更清晰）。 - Daniel Fischermin。 - Daniel FischerA = ceiling(sum/k) 开始。在第一个 running_sum[i] 超过 A 的点，计算 B = ceiling((sum-running_sum[i-1])/(k-1))。如果 B >= running_sum[i]，则不需要分支并且可以更新 A = running_sum[i]。类似地，在后续交叉点，如果剩余的平均值大于通过交叉获得的平均值，则无需分支。 - Daniel FischerA = max{ max array, ceiling(sum/k) }，不要运行到只剩下少量元素的子数组。那么我仍然认为它非常好。 - Daniel Fischer这只是一个想法的草图...我不确定它是否有效，但它非常简单（而且可能也很快）。
首先将分隔符均匀分布（实际上开始的方式并不重要）。
对每个子数组求和。
找到和最大的子数组。
查看右侧和左侧相邻的子数组，并在左侧的子数组比右侧的子数组和低（反之亦然）时将分隔符向左移动一位。
针对当前具有最大和的子数组重新执行此操作。
你会遇到一些情况，其中你将保持在同样的两个位置之间来回弹跳，这可能意味着你已经找到了解决方案。
编辑：请参见@rds的评论。您需要更加努力地思考弹跳解决方案和结束条件。
如果您的数组有随机数，您可以希望每个子数组都有n/k是一个好的起点。
从那里开始
我的想法，可惜不起作用：
2 | 1 1 | 2 3作为第一步，并以2 1 1 | 2 | 3或2 | 1 1 2 | 3结束。然后，您需要检查是否可以通过移动边界来减小最大值。这将为移动边界提供一个良好的起点，而且在大多数情况下，您很快就会找到最佳解，但我不确定是否存在一些情况，您会陷入局部但不是全局最小值的情况。 - Daniel Fischer