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

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)。

我尝试创建一个贪婪算法，该算法通过对所有整数求和并将其除以子数组的结果数量来计算整个数组的平均值。所以在上面的例子中，这意味着 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;

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

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

Algorithm splitting array into sub arrays where the maximum sum among all sub arrays is as low as possible

arrays

algorithm

split

sum

min