Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

 public int splitArray(int[] nums, int m) {
       // 1 5 9
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        return binary(nums, m, sum, max);
        
    }
    // 10, 24
    // 
    
    private int binary(int[] nums, int m, int high, int low) {
        int mid = 0;
        
        while (low <= high) {
            mid = low + (high - low) / 2;
           if (valid(nums, m, mid)) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
           
        }
         return low;
    }
    
    private boolean valid(int[] nums, int m, int subArraySum) {
        int curSum = 0, count = 1;
        for (int num : nums) {
            curSum += num;
            if (curSum > subArraySum) {
                curSum = num;
                count++;
               if (count > m) {
                   return false;
               }
            }
        }
        return true;
    }