算法将数组拆分为子数组，其中所有子数组之间的最大和尽可能小 [英] 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.

我尝试创建一个贪心算法，通过将所有整数相加并将其除以子数组的结果数量来计算整个数组的平均值.所以在上面的例子中，这意味着 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屋！