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.

S: Binary Search +　greedy O(nlogn)

left = 数组中最大的元素， right = 数组所有元素之和，不管怎么划分，non-empty continuous subarray sum一定在[let, right]区间。对此区间进行二分查找：

若可以用m-1次cut将数组分为m份，每份的sum都小于或等于mid，则所求target一定小于等于mid，否则所求target一定大于mid。left，right为target的boundary，最终结果一定在left和right中

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int left = 0, right = 0;
        for (int i : nums) {  //find left, right boundary
            left = max(i, left);
            right += i;
        }
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (doable(nums, m - 1, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (doable(nums, m - 1, left)) {
            return left;
        } else {
            return right;
        }
    } 

private:
    bool doable(vector<int>& nums, int cuts, int maxSum) {  //greedy aproach
        int curSum = 0;
        for (int i : nums) {
            if (curSum + i <= maxSum) {
                curSum += i;
            } else {  //add one cut, new segment start at i
                cuts--;
                curSum = i;
                if (cuts < 0) {
                    return false;
                }
            }
        }
        return true;
    }
};