410.Split Array Largest Sum¶

410.Split Array Largest Sum¶

Tags: Hard Binary Search Dynamic Programming

Company: Baidu Facebook

Links: https://leetcode.com/problems/split-array-largest-sum/

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note: If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long long left = 0, right = 0;
        for (int i = 0; i < nums.size(); ++i) {
            left = max(static_cast<int>(left), nums[i]);
            right += nums[i];
        }

        while (left < right) {
            long long mid = left + ((right - left) >> 1);
            if (canSplit(nums, m, mid)) right = mid;
            else left = mid + 1;
        }

        return left;
    }

    bool canSplit(vector<int> & nums, int m, long long target) {
        int cnt = 1;
        long long curSum = 0;
        for (auto e : nums) {
            curSum += e;
            if (curSum > target) {
                curSum = e;
                ++cnt;
            }
            if (cnt > m) return false;
        }

        return true;
    }
};

卡边界，如果 $m = 1$ ，则相当于是整个数组，因为所有数字非负，所以肯定是最大值。如果 $m = n$ ，也就是数组的每个元素单独成一个子数组，那么相当于找数组里元素的最大值。那么其他情况，肯定是在这个范围之间。所以考虑二分查找。

用一个例子来分析，nums = [1, 2, 3, 4, 5], m = 3，将 left 设为数组中的最大值5，right 设为数字之和 15，然后算出中间数为 10，接下来要做的是找出和最大且小于等于 10 的子数组的个数，[1, 2, 3, 4], [5]，可以看到无法分为3组，说明 mid 偏大，所以让 right=mid，然后再次进行二分查找，算出 mid=7，再次找出和最大且小于等于7的子数组的个数，[1,2,3], [4], [5]，成功的找出了三组，说明 mid 还可以进一步降低，让 right=mid，再次进行二分查找，算出 mid=6，再次找出和最大且小于等于6的子数组的个数，[1,2,3], [4], [5]，成功的找出了三组，尝试着继续降低 mid，让 right=mid，再次进行二分查找，算出 mid=5，再次找出和最大且小于等于5的子数组的个数，[1,2], [3], [4], [5]，发现有4组，此时的 mid 太小了，应该增大 mid，让 left=mid+1，此时 left=6，right=5，循环退出了，返回 right 即可.

DP 的解法，相对来说，这种方法应该更容易理解一些。建立一个二维数组 dp，其中 $dp[i][j]$ 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值，初始化为整型最大值，如果无法分为i组，那么还是保持为整型最大值。为了能快速的算出子数组之和，还是要建立累计和数组，难点就是在于推导状态转移方程了。来分析一下，如果前j个数字要分成i组，那么i的范围是什么，由于只有j个数字，如果每个数字都是单独的一组，那么最多有j组；如果将整个数组看为一个整体，那么最少有1组，所以i的范围是[1, j]，所以要遍历这中间所有的情况，假如中间任意一个位置k， $dp[i-1][k]$ 表示数组中前k个数字分成 i-1 组所能得到的最小的各个子数组中最大值，而 sums[j]-sums[k] 就是后面的数字之和，取二者之间的较大值，然后和 dp[i][j] 原有值进行对比，更新 $dp[i][j]$ 为二者之中的较小值，这样k在 [1, j] 的范围内扫过一遍，dp[i][j] 就能更新到最小值，最终返回 $dp[m][n]$ 即可。但是这种方法显然速度太慢。

Runtime: 136 ms, faster than 28.56% of C++ online submissions for Split Array Largest Sum.
Memory Usage: 9.3 MB, less than 30.00% of C++ online submissions for Split Array Largest Sum.

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<long long> sums(n + 1, 0);
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = i - 1; k < j; ++k) {
                    long long val = max(dp[i - 1][k], sums[j] - sums[k]);
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }
        return dp[m][n];
    }
};