假设我们有一个整数数组：a = {2,4,3,5}
我们有k = 3。
我们可以将数组a拆分为k（3）个子数组，其中数组的顺序无法更改。每个子阵列的总和必须尽可能低，以使所有子阵列之间的最大总和尽可能低。
对于上述解决方案，这将给出{2，4}，{3}，{5}，其最大和为6（4 + 2）。
错误的答案将是{2}，{4、3}，{5}，因为在这种情况下，最大总和为7（4 + 3）。
我尝试创建一个贪心算法，该算法通过将所有int相加并将其除以子数组的结果数量来计算整个数组的平均值。因此，在上面的示例中，这意味着14/3 = 4（整数除法）。只要它小于平均数，它就会将数字加到计数器上。然后它将为子数组的其余部分重新计算。
我的解决方案给出了一个很好的近似值，可以用作启发式方法，但并不总是能给我正确的答案。
有人可以帮我解决一个算法，该算法为所有情况提供最佳解决方案，并且优于O（N²）吗？我正在寻找一种近似为O（n log n）的算法。
提前致谢！
我们可以使用二进制搜索来解决此问题。
因此，假设所有子数组的最大值为x，那么，我们可以贪婪地选择O（n）中的每个子数组，以使每个子数组的总和最大且小于或等于x。创建所有子数组后，如果子数组的数量小于或等于k，x则一种可能的解决方案，否则，我们增加x。
x
k
伪代码：
int start = Max_Value_In_Array; int end = Max_Number; while(start <= end) int mid = (start + end)/2; int subSum = 0; int numberOfSubArray = 1; for(int i = 0; i < n; i++){ if(subSum + data[i] > mid){ subSum = data[i]; numberOfSubArray++; }else{ subSum += data[i]; } } if(numberOfSubArray <= k) end = mid - 1; else start = mid + 1;
具有k的时间复杂度O（n log k）是最大可能和。
