题目描述

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

说明

数组长度 n 满足以下条件:

• 1 <= n <= 1000
• 1 <= m <= min(50, n)

样例

输入：
nums = [7,2,5,10,8]
m = 2

输出：
18

解释：
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

算法

(二分答案) $O(n \log (\sum nums[i]))$

1. 如果给定一个子数组和的上限，则可以很容易在线性时间内贪心判定是否可以分成 m 份。
2. 很容易发现这个上限对于可划分性是单调的，如果上限为 s 可以划分，则上限大于 s 都是可以划分的。
3. 至此可以二分这个上限，从数组中的最大值到数组所有元素的总和作为二分的上下界。对于给定的上限 mid，进行贪心的划分，如果划分的个数小于等于 m，则 r = mid；否则 l = mid + 1；

时间复杂度

• 每次需要线性时间判定，故时间复杂度为 $O(n \log (\sum nums[i]))$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    #define LL long long
    int check(const vector<int>& nums, LL max_sum) {
        int n = nums.size(), cnt = 1;
        LL tot = 0;
        for (int i = 0; i < n; i++) {
            if (tot + nums[i] > max_sum) {
                cnt++;
                tot = nums[i];
            }
            else {
                tot += nums[i];
            }
        }
        return cnt;
    }

    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        LL l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            l = max(l, (LL)(nums[i]));
            r += nums[i];
        }

        while (l < r) {
            LL mid = (l + r) >> 1;
            if (check(nums, mid) <= m)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};