将数组拆分为子数组的算法，其中所有子数组之间的最大和尽可能低

假设我们有一个整数数组：a = {2,4,3,5}

我们有 k = 3。

我们可以将数组a分割成k(3)个子数组，其中数组的顺序不能改变。每个子数组的和必须尽可能小，以便所有子数组之间的最大和尽可能小。

对于上述解决方案，这将给出 {2, 4}, {3}, {5}，其最大总和为 6 (4 + 2)。

错误答案为 {2}, {4, 3}, {5}，因为在本例中最大和为 7 (4 + 3)。

我尝试创建一个贪婪算法，该算法通过将所有整数相加并将其除以子数组的结果数量来计算整个数组的平均值。因此，在上面的示例中，这意味着 14 / 3 = 4（整数除法）。然后，只要数字小于平均数，它就会将数字添加到计数器中。然后它将重新计算子数组的其余部分。

我的解决方案给出了一个很好的近似值，可以用作启发式，但并不总是能给我正确的答案。

有人可以帮我找到一种算法，它可以为我提供所有情况下的最佳解决方案，并且比 O(N²) 更好吗？我正在寻找一种大约为 O(n log n) 的算法。

提前致谢！

我们可以使用二分查找来解决这个问题。

因此，假设所有子数组的最大值为x，因此，我们可以在 O(n) 中贪婪地选择每个子数组，使得每个子数组的和最大且小于或等于x。创建完所有子数组后，如果子数组的个数小于等于k, so x是一种可能的解决方案，否则，我们增加x.

伪代码：

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;

时间复杂度 O(n log k)，其中 k 是可能的最大总和。