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