Back to DSA

Split Array Largest Sum

hard
Acceptance: 44%
Binary SearchDynamic Programming

Given an integer array and a number k, divide the array into exactly k contiguous segments (each non-empty). Among all possible divisions, minimize the largest segment sum. Return that minimized value.

Examples

Example 1:
Input:nums = [2,3,1,2,4,3], k = 3
Output:6
Explanation: Splitting as [2,3,1],[2,4],[3] gives segment sums 6,6,3. The largest is 6, which is optimal.
Example 2:
Input:nums = [1,4,4], k = 3
Output:4
Explanation: Each element is its own segment, so the largest sum is 4.

Hints

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumEdit Distancehard
00:00
class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int n : nums) { lo = Math.max(lo, n); hi += n; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 1, sum = 0;
            for (int n : nums) {
                if (sum + n > mid) { count++; sum = 0; }
                sum += n;
            }
            if (count <= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
Time complexityO(n * log(sum - max))
Space complexityO(1)