Description:

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)

Example:

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.

Link:

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

解題方法：

二分法：
假設(shè)給定一個(gè)值n, 來(lái)對(duì)整個(gè)數(shù)組進(jìn)行劃分，要求每個(gè)子數(shù)組的和都不超過(guò)n，那么能劃分出多少個(gè)子數(shù)組肯定存在一個(gè)下限m_min(即最少能劃分出幾個(gè)子數(shù)組)，而這道題其實(shí)就是求當(dāng)給定一個(gè)m的時(shí)候，n最小是多少。
我們可以知道，當(dāng)n越大，m_min就越小，當(dāng)n等于整個(gè)數(shù)組的和的時(shí)候，m_min == 1。所以我們知道n的最大值為整個(gè)數(shù)組之和。
當(dāng)n越小，m_min就越大，因?yàn)槊總€(gè)子數(shù)組能包含的數(shù)就越少，就要做更多的劃分。當(dāng)n < 數(shù)組最大的數(shù)的時(shí)候，我們甚至都不能劃分，所以綜上所述，數(shù)組最大的數(shù)<=n<=數(shù)組之和。

那么當(dāng)給定一個(gè)n的時(shí)候，我們可以求出其能做出的最小劃分m_min：用貪心就可以求出，時(shí)間復(fù)雜度為nums.size()。

所以這道題就變成了，在一個(gè)遞增區(qū)間查找n, 使得m_min <= m, 所以，我們可以用二分查找來(lái)解決這道題。

Time Complexity：

NlogN

完整代碼：

int splitArray(vector<int>& nums, int m) {
    long start = 0, end = 0;
    for(auto num: nums) {
        start = start > num ? start : num;
        end += num;
    }
    while(start + 1 < end) {
        long mid = start + (end - start) / 2;
        long checkR = check(nums, mid);
        if(checkR <= m)
            end = mid;
        else
            start = mid;
    }
    if(check(nums, start) <= m)
        return start;
    else
        return end;
}
int check(vector<int>& nums, long m) {
    long sum = 0;
    int cnt = 1;
    for(int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        if(sum > m) {
            sum = nums[i];
            cnt++;
        }
    }
    return cnt;
}