The problem
Split an array into k contiguous subarrays minimizing the LARGEST subarray sum. Return that minimized maximum.
Stuck? Reveal hints one at a time
How to approach it
- 1Search space: lo = max(nums) (a piece must hold the biggest element), hi = sum(nums).
- 2feasible(cap): greedily pack elements into the current piece until adding one would exceed cap, then start a new piece; count pieces ≤ k?
- 3Binary search the smallest feasible cap.
Key insight
Greedy packing is provably optimal for the CHECK (fewest pieces for a given cap), which is all binary search needs — optimality of the final answer comes from the search, not the greedy.
The solution
Watch out for
- lo must start at max(nums), not 0 — otherwise feasible() can loop with an impossible cap.
- The O(k·n²) DP works but is strictly dominated; mention it as the "before" solution.