410. Split Array Largest Sum

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;	}};