410. 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.

Binary Search + Greedy是效率比較高的方法，假設把nums array分成每個數字自己一組(m = nums.size())，這樣最大的subarray就是數列裡最大的數。如果所有數字看作一組(m = 1)，那最大的subarray就是所有數字的總和。那麼這題要求的值必然介於上面兩個值之間。所以我們可以先界定出二分查找法的左右邊界。

每一個binary search iteration都會藉由當前的左右邊界找出一個中間值，會loop through所有數字一遍看看是否能找到subarrays的最大的和且小於等於當前mid值。

// Binary Search + Greedy
bool canSplit(int target, vector<int>& nums, int m) {
    int cnt = 1;
    long long curSum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        curSum += nums[i];
        if (curSum > target) {
            curSum = nums[i];
            ++cnt;
            if (cnt > m) return false;
        }
    }
    return true;
}
int splitArray(vector<int>& nums, int m) { // time: O(nlogn); space: O(1)
    long long left = 0, right = 0;
    for (int num : nums) {
        left = max(left, (long long)num);
        right += num;
    }
    if (m == 1) return (int)right;
    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (canSplit(mid, nums, m)) right = mid;
        else left = mid + 1;
    }
    return (int)left;
}

這題也可以用Dynamic programming來做，dp[i][j]代表前j個數字形成的i個子數列中最小的子陣列最大和。

假設k為中間任意數量的數字，dp[i - 1][k]代表前k個數字形成的i-1個子數列中最小的最大子數列和。

sums[j] - sums[k]就是最後一個子數列的和。要跟前i - 1個子數列比較紀錄最大值。最後再跟當前的dp[i][j]結果比較紀錄最小值。

// Dynamic programming
int splitArray(vector<int>& nums, int m) { // time: O(m * n^2); space: O(m * n)
    int n = nums.size();
    vector<long> sums(n + 1, 0);
    // dp[i][j] means the smallest max value in i subarrays split by the first j numbers in nums array
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, INT_MAX));
    dp[0][0] = 0; // Initiailization
    // build sums array
    for (int i = 1; i <= n; ++i) {
        sums[i] = sums[i - 1] + nums[i - 1];
    }
    for (int i = 1; i <= m; ++i) { // i subarrays
        for (int j = 1; j <= n; ++j) { // first j numbers in nums array
            for (int k = i - 1; k < j; ++k) { // the kth number in nums array
                // sums[j] - sums[k] calculates the last subarray in current consideration
                int val = max(dp[i - 1][k], (int)(sums[j] - sums[k])); // minmax
                dp[i][j] = min(dp[i][j], val); // max
            }
        }
    }
    return dp.back().back();
}