https://leetcode.com/submissions/detail/90614988/

Split_Array_Largest_Sum.java

/**
 * https://leetcode.com/submissions/detail/90614988/
 * 二分 + 确界 判断
 */
public int splitArray(int[] nums, int m) {
        long right = 1;//右界是总和
        for(int i = 0; i<nums.length; ++i){
            right +=nums[i];
        }
        long left = 0,ans = 0;
        while(left < right){
            long mid = (left + right) / 2;
            if(guess(mid, nums, m)){
                ans = mid;
                //left = mid + 1;
                right = mid;
            } else {
                //right = mid - 1;
                left = mid + 1;
            }
        }
        return (int)ans;
    }
    
    /**
     * 在某个ans = mid确定的情况下,判断当前mid是否满足所给的m个子数组的条件
     * 满足则返回true
     * 否则返回false 继续二分
     */
    public boolean guess(long mid, int[] nums, int m){
        long sum = 0;//和
        for(int i = 0; i<nums.length;++i){
            if(sum + nums[i] > mid){//当前nums[i]元素不能再放入一个子数组
                --m;//消耗一个子数组存放
                sum = nums[i];
                if(nums[i] > mid){//单个元素大于mid,则mid无效
                    return false;
                }
            } else {
                sum += nums[i];
            }
        }
        return m>=1;//这时sum一定不为0,则至少需要1个子数组存放
    }