「最大化最小值」或者「最小化最大值」采样二分

分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小

思路：段数分的越多，最大值就越小，从不分段开始找，l为Math.max(mx-1, (sum-1)/k)，r为sum。检验分段是否小于mid，小于r=mid。大于l=mid。
检验是否满足mid为前面的数字和sum不大于mid且段落数小于k。

class Solution {
    public int splitArray(int[] nums, int k) {
        int sum = 0;
        int mx = 0;
        for(int x:nums) {
            sum += x;
            mx = Math.max(mx, x);
        }

        int left = Math.max(mx-1, (sum-1)/k);

        int right = sum;

        while(left+1<right) {
            int mid = left + (right-left) / 2;
            if(check(nums, k, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int k, int mx) {
        int cnt = 1;
        int s = 0;
        for(int x:nums) {
            if(s+x<=mx) {
                s +=x;
            } else {
                if(cnt == k) return false;
                cnt +=1;
                s = x;
            }
        }
        return true;
    }
}