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

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

Examples:

Input:nums = [7,2,5,10,8]m = 2Output:18Explanation: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.
Subscribe to see which companies asked this question.
將給定的序列分成m個子序列，使得各個序列的總和的最大值最小，求出這個最小的最大值。看了discuss才知道怎樣用二分法做，答案一定是在Max（序列的最大值）和sum（序列總和）之間，在這個范圍內進行二分搜索。對于當前的值d，如果序列能分成m個和小于等于d的序列，則表示當前值是“有效的”，可以進一步減少來尋找最終答案；如果不能，即分成多于m個和小于等于d的序列，則當前值比答案小，增大之尋找最終答案。最后縮到一個值，判斷這個值是否“有效”，“有效”的話答案是這個值，否則是這個值加1.
代碼：
class Solution {public:	int splitArray(vector<int>& nums, int m) 	{		int sum = 0, Max = 0;		for(auto num:nums)		{			sum += num;			Max = max(Max, num);		}		int l = Max, r = sum;		while(l < r)		{			int mid = l + (r - l) / 2;			bool b = isvalid(nums, m, mid);			if(b)			{				r = mid - 1;			}			else			{				l = mid + 1;			}		}		return isvalid(nums, m, l) ? l : l+1;	}PRivate:	bool isvalid(vector<int>& nums, int m, int d)	{		int sum = 0;		for(auto num:nums)		{			if(sum + num > d)			{				--m;				sum = 0;			}			if(m == 0) return false;			sum += num;		}		return true;	}};