Split Array Largest Sum
Split nums into k non-empty contiguous subarrays so that the largest subarray sum is as small as possible. Return that minimised largest sum.
Intuition
The phrase minimise the maximum is the signature of binary search on the answer. Rather than searching over the exponentially many ways to place k-1 cut points, guess a ceiling for the largest allowed subarray sum and ask a much easier question: greedily filling subarrays up to that ceiling, how many subarrays do we need? If that count is at most k, the ceiling is achievable. Raising the ceiling never increases the count, so the feasible ceilings form a suffix — binary search finds its start.
Binary search on the answer, identical in shape to Capacity to Ship Packages. The feasibility check greedily fills each piece until it would overflow, and the bounds come from the physics: no smaller than the largest element, no larger than the total.
Approach
Recognise the structure and set the bounds
The answer cannot be less than max(nums) — some subarray must contain the largest element, so the largest sum is at least that. And it cannot exceed sum(nums), which is what you get with k = 1. So the answer lives in [max(nums), sum(nums)], a range we can binary search even though the array itself is unsorted. Note this is the identical structure to Allocate Minimum Pages, just with different vocabulary.
Count the pieces a ceiling forces
Given a ceiling, walk the array accumulating a running sum. When adding the next element would exceed the ceiling, close the current subarray and start a new one with that element. This greedy is optimal for a fixed ceiling: closing a subarray earlier than forced can only lead to needing more subarrays, never fewer. The resulting count is the minimum number of pieces achievable under that ceiling.
Binary search the ceiling
If the count is at most k, the ceiling works — record it and try a lower one to squeeze further. (Using fewer than k pieces is fine: you can always split an existing piece further, which never raises the maximum.) If the count exceeds k, the ceiling is too tight and must go up. O(n log sum) total, against O(n^2 k) for the DP formulation.
Solution & live demo
Common pitfalls
Starting lo at 0 or 1
lo, hi = 0, sum(nums)
lo, hi = max(nums), sum(nums)
Elements can't be split, so any cap below the largest one makes the greedy check loop without ever placing it. max(nums) is the smallest feasible answer.
Starting the piece count at 0
pieces, run = 0, 0
pieces, run = 1, 0
The first subarray exists before any split is made. Counting from 0 reports one fewer piece than reality and accepts caps that need k + 1 subarrays.
Trying interval DP
dp[i][j] = min over splits
while lo <= hi:
cap = (lo + hi) // 2The DP is O(n²k) and correct but far heavier. Because feasibility is monotone in the cap — a larger cap never needs more pieces — binary search answers it in O(n log(sum)).
Edge cases
The answer is sum(nums) — the top of the range. The feasibility check reports 1 piece for every ceiling at or above the total.
Every element becomes its own subarray, so the answer is max(nums) — the bottom of the range.
No split can accommodate it, so the check must report infeasible rather than looping forever. Starting lo at max(nums) makes this unreachable, but guarding explicitly is safer.
Still feasible — surplus subarrays can be created by splitting any existing one, which never increases the maximum sum.