LeetCode410. 分割数组的最大值

这道题看着好像没什么思路，但其实可以利用二分法来做，二分法中的mid就是最终要返回的值，也就代表着子数组的和最小的值

我们首先还是设置左右区间，左区间L=0，右区间是数组所有元素的和再加1，因为二分法的区间一般是左闭右开

然后就是将数组进行打包，从第一个开始打包，如果第一个加上后一个还不大于mid，那就将其继续加上后一个，直到大于mid了，那就说明这个包已经放不下了，后面的至少还需要再开一个包，每开一个包，m的数量就减少一个，最后return m究竟是否大于0

如果返回的是true，那我们再试试mid更小的时候是否也成立，将R = mid，把mid的值赋给R；如果返回的是false，说明mid太小了，那我们应该把mid稍微放大一点，看看还行不行，将L = mid + 1，把mid+1的值赋给L。最终mid的值就是所求的值。建议带入样例自己模拟一遍这个过程

class Solution {
    public boolean guess(long mid,int[] nums,long m) {
        long sum = 0;
        for(int i = 0;i < nums.length;i++) {
            if(sum + nums[i] > mid) {
                --m;
                sum = nums[i];
                if(sum > mid)
                    return false;
            }
            else
                sum += nums[i];
        }
        return m > 0;
    }
    public int splitArray(int[] nums, int m) {
        long ans = 0;
        long L = 0,R = 1;
        for(int i = 0;i < nums.length;i++) 
            R += nums[i];
        while(L < R) {
            long mid = (L + R) / 2;
            if(guess(mid,nums,m)) {
                ans = mid;
                R = mid;
            }
            else
                L = mid + 1;
        }
        return (int)ans;
    }
}