410. Split Array Largest Sum

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.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 106

• 1 <= m <= min(50, nums.length)

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 106

• 1 <= m <= min(50, nums.length)

Constraints:

Input: nums = [1,4,4], m = 3
Output: 4

Solution

The question is to find the maximum range sum among m subRanges. And we require to let the sum of each range be as small as possible.

That is the given maximum range sum k; all the range sum shall be small or equal to this sum. Then if we split the original array with k, it must be able to split the array into m subRanges.

Thus, a binary search approach can be applied. Given that if the k is fulfilled requirement, the subRanges number must be equal to m. if the number is less than m, it means the k is too big, if the number is larger than m, then the k is too small.

We can apply binary search to find the smallest one k let the number of sumRange >= m;

 public int splitArray(int[] nums, int m) {
        int min = 0, max = 0;
        for(int num : nums){
            min = Math.max(min, num);
            max += num;
        }
        
        while(max > min){
            int mid = min + (max-min)/2;
            if(isfeasible(mid, nums, m)){
                max = mid;
            }
            else{
                min = mid+1;
            }
        }
        return min;
    }
    
    public boolean isfeasible(int threshold, int[] nums, int m){
        int count = 1;
        int curSum = 0;
        for(int num : nums){
            curSum += num;
            if(curSum > threshold){
                count++;
                curSum = num;
            }
        }
        return count <= m;
    }