算法将数组拆分为子数组，其中所有子数组中的最大和尽可能小 [英] Algorithm splitting array into sub arrays where the maximum sum among all sub arrays is as low as possible

问题描述

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

Let's say we have an array of ints: a = {2,4,3,5}

我们有k = 3.

我们可以将数组a拆分为k(3)个子数组，其中数组的顺序无法更改.每个子阵列的总和必须尽可能小，以使所有子阵列中的最大总和尽可能小.

We can split array a in k (3) sub arrays in which the order of the array cannot be changed. The sum of each sub array has to be as low as possible so that the maximum sum among all sub arrays is as low as possible.

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

For the above solution this would give {2, 4}, {3}, {5} which has a maximum sum of 6 (4 + 2).

错误的答案将是{2}，{4、3}，{5}，因为在这种情况下，最大和为7(4 + 3).

A wrong answer would be {2}, {4, 3}, {5}, because the maximum sum is 7 (4 + 3) in this case.

我尝试创建一个贪心算法，该算法通过将所有int相加并将其除以子数组的结果数量来计算整个数组的平均值.因此，在上面的示例中，这意味着14/3 = 4(整数除法).然后，只要<<比平均数.然后，它将为子数组的其余部分重新计算.

I've tried creating a greedy algorithm which calculates the average of the entire array by summing all ints and dividing it by the resulting amount of sub arrays. So in the example above this would mean 14 / 3 = 4 (integer division). It will then add up numbers to a counter as long as it's < than the average number. It will then recalculate for the rest of the sub array.

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

My solution gives a good approximation and can be used as heuristic, but will not always give me the right answer.

有人可以通过一种算法为我提供帮助，该算法为所有情况提供最佳解决方案，并且优于O(N²)吗?我正在寻找一种近似为O(n log n)的算法.

Can someone help me out with an algorithm which gives me the optimal solution for all cases and is better than O(N²)? I'm looking for an algorithm which is O(n log n) approximately.

提前谢谢！

推荐答案

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

We can use binary search to solve this problem.

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

So, assume that the maximum value for all sub-array is x, so, we can greedily choose each sub-array in O(n) so that the sum of each subarray is maximum and less than or equals to x. After creating all subarray, if the number of sub-array is less than or equal to k, so x is one possible solution, or else, we increase 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是最大可能的和.

Time complexity O(n log k) with k is the maximum sum possible.

这篇关于算法将数组拆分为子数组，其中所有子数组中的最大和尽可能小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！