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

Question

假设我们有一系列整数:a = {2,4,3,5}

我们有k = 3.

我们可以在k(3)子数组中拆分数组a,其中数组的顺序不能改变.每个子阵列的总和必须尽可能低,以便所有子阵列中的最大总和尽可能低.

对于上述解决方案,这将给出{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;

具有k的时间复杂度O(n log k)是可能的最大总和.