/**
1. 各自和的最大值最小 -> 和趋近与平均值时和最小 -> 平均值不一定能被取到, 但一定在一个范围内
2. 考虑极端情况:
    2.1 m == 1时, 最大值为整个数组的和 sums          -> 结果的上界
    2.2 m == n时, 最大值为数组中最大的值MAX(nums[i]) -> 结果的下界
3. 二分验证答案 -> lowerBound 是否能将分割成 k份, k <= m 即可, 如果k < m 可以再次进行划分使其等于m
*/

/**
testcase
1. m == 1,n, random
2. n == 1, 1000, random
3. nums[i] == 1, Integer.MAX_VALUE, random, avg
*/


class Solution {
    public int splitArray(int[] nums, int m) {

        return divide(nums, m);
    }

    public int divide(int[] nums, int m){
        long sum = 0, max = 0;
        for (int i = 0; i < nums.length ; i++) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        int result = lowerBound(nums, m, max, sum);
        return result;
    }

    public int lowerBound(int[] nums, int m, long l, long r){
        while (l < r){
            long mid = l + r >> 1;
            if (check(nums, m , mid)) r = mid;
            else l = mid + 1;
        }
        return (int)l;
    }

    boolean check(int[] nums, int m, long target){
        long cur = 0, cnt = 0;
        for (int i = 0 ;i < nums.length ; i++){
            if (cur + nums[i] <= target) {
                cur += nums[i];
            } else {
                m -- ;
                cur = nums[i];
            }
        }
        return m >= 1 ;
    }
}