当一个数组被分成 K subarrays/groups 时，最大化所有子数组中的最小子数组和

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 < K，这意味着我们需要降低mid。

如果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个子数组，并且每个子数组的最小和值可能不同。

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

在这个特定问题中，最不可能的答案实际上是数组中的最小值，但可以毫无问题地使用 0。最大可能的答案是数组中所有值的总和。（即，if K==1）所以你检查那些可能的答案，看看是否可以将数组划分为 K 个子数组，最小的子数组和为 mid，这是当前的潜力回答你正在检查。 space个可能的答案适合这种二分查找策略，因为直到某个值v，和大于等于mid的子数组的个数小于K。从值 v 开始，您实际上可以有 >= K 个总和大于或等于 mid.

的子数组

在每一步（即二分搜索的迭代）中，您尝试分组，使每个组的总和为 >= mid。一旦一个组的总和超过该阈值，您就会开始一个新组。所以，从某种意义上说，你是对的，因为对于 mid 的特定值，只有一种最佳方法来划分数组：确保每个子数组都有一个总和>= K 一旦满足这个要求，就开始从原始数组中划分出一个新的子数组。这是确保全局最优结果的局部最优策略。（即贪心）但真正确保最大化最小子数组和的是二进制搜索。通过迭代 space 个可能的答案，并在完成后选择最不可接受的值，二分搜索确保在满足给定约束的答案中，最小的一个（即 v）被选中了。

如果你还在难以消化这个算法的策略，试着换个角度来考虑。这不是您要查找的分区，而是您可以为其创建 K 个连续组的最小值 v，每个组的总和将大于或等于 v。为了确保给定的 mid 有尽可能多的 可接受的 子数组，只要满足要求（即 sum >= mid），您就会不断向子数组添加新元素未满足，并在子阵列达到该阈值后立即开始形成新的子阵列。因此，对于每个 mid、numOfSubArrays returns，您可以组成最大数量的 可接受 组。总的来说，二进制搜索只是找出值 v，numOfSubArrays returns 大于或等于 K.

的最小值

当一个数组被分成 K subarrays/groups 时，最大化所有子数组中的最小子数组和

Maximize the minimum subarray sum out of all subarrays when an array is divided into K subarrays/groups

algorithm

binary-search

greedy