Split Array Largest Sum
Hard · Binary Search · Array · Binary Search · Dynamic Programming · Greedy · Prefix Sum
Problem
You are given an integer array nums and an integer k. Split nums into exactly k non-empty, contiguous subarrays.
Each split has a largest subarray sum. Return the smallest possible value of that largest sum, over all ways to split.
Examples
Input: nums = [3,1,4,1,5,9], k = 3 Output: 9
[3,1,4,1], [5] and [9] have sums 9, 5 and 9. No split does better: the part holding 9 sums to at least 9.
Input: nums = [2,2,2,2], k = 2 Output: 4
Cutting in the middle gives two parts that sum to 4 each.
Input: nums = [1,2,3,4], k = 1 Output: 10
With k = 1 the only split is the whole array, whose sum is 10.
Constraints
- 1 <= len(nums) <= 1000
- 0 <= nums[i] <= 10^6
- 1 <= k <= min(50, len(nums))
Approaches
- Baseline: DP over prefixes and part counts — time O(k · n²), space O(k · n)
Follow-up
The DP version also tells you where to cut; the binary search only gives the value. How would you recover an optimal split from the binary search's answer?
Related problems
Start free on Cariara · Coding problems · System design studio
