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

Question

假设我们有一个整数数组：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）的算法。

提前致谢！

Answer 1

我们可以使用二进制搜索来解决此问题。

因此，假设所有子数组的最大值为x，那么，我们可以贪婪地选择O（n）中的每个子数组，以使每个子数组的总和最大且小于或等于x。创建所有子数组后，如果子数组的数量小于或等于k，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;

具有k的时间复杂度O（n log k）是最大可能和。