将数组划分为k个连续分区，以使最大分区的总和最小

Question

这里最大和子集是k个子集之一，它给出最大和，例如：arr = [10,5,3,7]和k =将arr划分为k个子集的2种可能方式是{10，[5,3,7]} ，{{10,5]，[3,7}，{[10,5,3]，7}和{[10,5]，[3,7}是最佳选择。编辑：它等效于 https://www.codechef.com/DI15R080/problems/MINMAXTF

Answer 1

这是一个二进制搜索样本空间的例子。

int min_max_sum(std::vector<int> & a, int K) {        

    int n = a.size();    
    long long high = 0, low = 0, mid = 0;

    for (int i = 0; i < n; ++i) {
        high += a[i];
        low = max(a[i], low);
    }

    while(low <= high) {
        mid = (low+high)/2;

        long long part_sum = 0;
        int parts = 1;
        for (int i = 0; i < n; ++i) {
            if (part_sum + a[i] > mid) {
                part_sum = 0;
                parts++;
            } else {
                part_sum += a[i];
            }
        }

        // if no. of parts in less than (or equal to) K then mid needs to (,or can) be more constrained by reducing upper limit
        if (parts <= K) {
            high = mid - 1;
        } else { 
            low = mid + 1;
        }
    }

    return mid;
}

复杂度：O(n log(sum(array)))。

但是由于对数比线性好成指数级，所以这种复杂度非常好。

最坏情况复杂度：O(n log(INT_MAX * n))=O(32 n +n log(n))=O(n log(n))。

Answer 2

假设您知道答案是x，这意味着最大子集的总和等于x。您可以通过贪婪算法O（n）验证此假设。（从左到右遍历该数组并选择项目，直到该子集的总和小于x为止）。现在，您可以二进制搜索在X和查找最小值X。该算法的复杂度为O（nlogn）。

Answer 3

这可以使用动态规划来解决：

让我们首先定义DP[n,m]将子数组划分为多个部分的最佳解决C[1..n]方案m。其中每个部分至少有一个元素。

DP[n,1] = sum(C1:Cn)
DP[n,n] = max(C1:Cn)
DP[n,m] = min( sum(Ck:Cn) + DP[k-1,m-1] )
          where k goes from m to n

解释：
DP[n,1] - 基本情况，当分区数量为 时，1只有一种方法 - 留下所有元素（从 1 到 n）。
DP[n,n]- 每当分区数量等于数组中剩余元素的数量时，只有一种合法的划分方法 - 每个元素位于不同的分区中，因此具有最大总和的分区是数组中的最大元素。
DP[n,m]- 这是主要的解决方案。我们不知道下一个分区将有多少个元素，因此我们需要检查所有选项并从中获取最小值。