当将数组划分为K个子数组/组时，最大化所有子数组中的最小子数组总和

Question

我的疑问与上述问题的框架更为相关。

用于解决上述问题的算法是二进制搜索。

 int low = 0, high = sum(A);
    while(low <= high) {
         int mid = low + (high-low)/2;
         if(numOfSubArrays(A, mid) <= K)
             high = mid-1;
         else
             low = mid+1;
     }
ans = low;

int numOfSubArrays(vector<int>& A, int sum) {
    int total = 0, count = 0;
    for(int num : A) {
       total += num;
       if(total >= sum) {
           total = 0;
           count++;
       }
    }
    return count;
}

我了解上述情况下的算法流程。

如果我们可以将A分为M部分和M ，则意味着我们需要降低中点。

如果M> K，我们需要增加中间值。

[M = K时，我们需要降低中间值以在所有子数组中找到最小和。

但是，对我来说，似乎只有一种方法可以将A分成K个部分，而子数组的最小和就是答案。

因此，“最大化图片的最小拟合度”一词的精确度如何？是什么确保子数组的最小和最大化？

Answer 1

首先，让我们从一个示例开始，该示例将测试您对于给定的A和K是否存在单一解决方案的直觉。

对于A=[1,2,3,4,5]和K=2，我们可以使分区P和最小子数组总和v如下：

P = [1], [2,3,4,5]  ; v = 1
P = [1, 2], [3,4,5] ; v = 3
P = [1,2,3], [4,5]  ; v = 6
P = [1,2,3,4], [5]  ; v = 5

如您所见，有多种方法可以将A划分为K子数组，并且每种方法可能具有不同的最小子数组总和值。

也就是说，我们现在可以分析此解决方案中发生的情况。该算法提出了一种通用方法。基本上，您有一个可接受的答案空间，然后使用二进制搜索在该空间中搜索最佳答案。

在此特定问题中，最小可能的答案实际上是数组中的最小值，但可以使用0而不出现任何问题。可能的最大答案是数组中所有值的总和。 （即，如果为K==1），那么您遍历那些可能的答案，看看是否可以将数组划分为K个子数组，最小的子数组总和为mid，这是您正在检查的当前潜在答案。可能答案的空间适用于此二进制搜索策略，因为直到某个值v，总和大于或等于mid的子数组的数量小于K。从v值开始，您实际上可以拥有>= K子数组，其总和大于或等于mid。

[在每个步骤（即，二进制搜索的迭代），您尝试形成组，使每个组的总和为>= mid。组的总和超过该阈值后，就可以开始创建一个新组。因此，从某种意义上来说，您是正确的，因为对于mid的特定值，只有一种optimal分区数组的方式：确保每个子数组都有一个总和>= K，并在此之后满足要求后，开始从原始数组中分区一个新的子数组。这是确保全局最佳结果的局部最佳策略。 （即贪婪）但是实际上确保最大化最小子数组总和的是二进制搜索。通过遍历可能答案的空间，并在完成后选择最不可接受的值，二进制搜索可确保在满足给定约束的答案中，选择最小的值（即v）。

如果您仍然难以理解该算法的策略，请尝试从另一个角度考虑它。它不是您要查找的分区，而是您可以为其创建v连续组的最小值K，每个组的总和将大于或等于v。为了确保给定的mid有尽可能多的acceptable子数组，只要不满足要求（即sum >= mid），就一直向该子数组添加新元素，并开始形成一个新的子数组，如下所示：子数组达到该阈值之后。因此，对于每个mid，numOfSubArrays会向您返回您可以形成的最大数量的[[accept]]组。总体而言，二进制搜索仅找出值v，这是numOfSubArrays返回大于或等于K的最小值。