小编典典

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

algorithm

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

提前致谢!


阅读 15

收藏
2020-07-28

共1个答案

小编典典

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

因此,假设所有子数组的最大值为x,那么,我们可以贪婪地选择O(n)中的每个子数组,以使每个子数组的总和最大且小于或等于x。创建所有子数组后,如果子数组的数量小于或等于kx则一种可能的解决方案,否则,我们增加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)是最大可能和。

2020-07-28

回答这个问题

Nothing to preview