DSA problem
Split Array Largest Sum
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.
This is the canonical "binary search the answer" problem on max-min objective. Let canSplit(cap) = "can we partition nums into at most k contiguous parts, each with sum at most cap?" The predicate is monotonic in cap: larger caps allow fewer parts. So the smallest cap that satisfies the predicate is the answer.
The predicate is a simple greedy. Walk left to right, accumulating a running sum; whenever adding the next element would exceed cap, start a new part. Count parts and return parts <= k. The greedy is optimal because we have no incentive to start a new part early — packing as much as possible into each part leaves the rest with as much slack as possible.
The search range for cap is [max(nums), sum(nums)]. The lower bound is forced: a single element exceeds cap if cap < max. The upper bound is trivial: one part of sum(nums) always works (when k >= 1). Use the lower-bound shape while (lo < hi), mid = lo + (hi - lo) / 2, set hi = mid on canSplit(mid) else lo = mid + 1.
The time complexity is O(n log(sum)). Use 64-bit arithmetic for sums in Java/C++ since n * max can exceed 2^31 - 1 (n up to 1000, values up to 10^6, so sum up to 10^9 fits in 32-bit but stays safer in long).
Examples
nums = [7,2,5,10,8], k = 218nums = [1,2,3,4,5], k = 29nums = [1,4,4], k = 34Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^6
- 1 <= k <= min(50, nums.length)
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.