410. Split Array Largest Sum

Given an array 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.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples: 

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.

Solution:

Assume that we have already split the array which satisfy the condition.

Let's say sub array sub is the one have the maximum sum of all sub arrays.

We know the sum of this array bound satisfies:

1. bound >= the largest element of the array.

2. bound <= the sum of the array.

Therefore, we can use binary search to find the first occurrence of bound that in the above range that can be splitter into m partitions.

The time complexity is O(nlogn) and the space complexity is O(1).



Code:

public class Solution {
    public int splitArray(int[] nums, int m) {
        int start = 0;
        int end = 0;
        for (int num : nums) {
            start = Math.max(start, num);
            end += num;
        }
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isValid(nums, mid, m)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return isValid(nums, start, m) ? start : isValid(nums, end, m) ? end : -1;
    }
    
    public boolean isValid(int[] nums, int bound, int m) {
        int count = 1;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (sum > bound) {
                count++;
                sum = num;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}