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.
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
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.