LeetCode

Split Array Largest Sum

Michael

Jun 2, 2023 • 1 min read

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.

public class Solution {
    public int splitArray(int[] nums, int m) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = 0;
        long sum = 0;
        
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }
        
        if (m == 1) {
            return (int)sum;
        }
        
        long left = max, right = sum;
        
        while (left <= right) {
            long middle = left + (right - left) / 2;
            
            if (valid(nums, m, middle)) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        
        return (int)left;
    }
    
    private boolean valid(int[] nums, int m, long target) {
        int count = 1;
        long sum = 0;
        
        for (int num : nums) {
            sum += num;
            
            if (sum > target) {
                sum = num;
                count++;
                
                if (count > m) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

Hope this helps,
Michael