将数组分割成子数组的算法，使所有子数组中最大的总和尽可能低。

Question

假设我们有一个int数组：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）的算法。

提前感谢！

- Robinhopok

---

你确定有一个O(n log n)的解决方案，还是希望有一个O(n log n)的解决方案？只是想要一个思考的方向。此外，子数组或int是否有任何限制？（为什么答案不是{2}，{3}，{4}，{5}，这样可以得到5作为答案？int是否非负等） - shole

是的，我确信有一个解决方案。我正在考虑使用贪心算法或分治算法。确实存在一些限制条件：

• 顺序不能改变。
• 分割数量是给定的，不能多也不能少（在我的例子中是3）。
• 所有整数都是正数（不知道这对解决方案是否重要）。

- Robinhopok

Answer 1

我们可以使用二分查找来解决这个问题。

因此，假设所有子数组的最大值为 x，我们可以贪心地选择每个子数组，使得每个子数组的和最大且小于或等于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是可能的最大和。

- Pham Trung

---

@Robinhopok，在找到最小值 x 后，你只需要按照计算子数组数量时的方式进行重构即可。 - Pham Trung

@PhamTrung 哦，我明白了，谢谢。我已经尝试在C#中实现该算法链接，但是它陷入了一个无限循环。我有什么遗漏吗？ - Robinhopok

@Robinhopok，你的程序可能会导致数字溢出。因为对于 end，你赋值了 int.MaxValue。 - Pham Trung

@Robinhopok 所以，对于这个问题，二分查找不是要在数组中查找任何元素，而是要查找最小的数字 x，使得我们可以将数组分成 k 段，其总和小于或等于 x。为什么可以在这种情况下使用二分查找？因为有一个属性，即对于一个值 x，如果我们可以将数组分成 k 段，那么对于值 大于 x，我们也可以将数组分成 k 段。因此，满足二分查找的要求。 - Pham Trung

@Robinhopok，那么问题是如何找到二分查找的“开始”和“结束”值。答案非常简单，“开始”值，在这种情况下，是x可以达到的最小可能值。由于数据数组只包含正数，选择一个比数组中最大元素或Max_Value_In_Array更小的值是没有意义的。同样，二分查找的“结束”值应该是x可能的最大值，而且，由于这个数组只包含正值，它是整个数组的总和。 - Pham Trung