visual walkthrough
Split Array Largest Sum
Minimise the maximum subarray sum; a classic Hard.
The idea
Turn "minimise the biggest part" into a yes/no: can the array be cut into at most k parts, each summing to ≤ limit?
A bigger limit never needs more parts, so binary search the smallest limit that says yes. Checking a limit is greedy: fill a part until the next number won't fit.
Complexity
| approach | time | space |
|---|---|---|
| Try every split | O(C(n, k)) | O(k) |
| Binary search the limit | O(n log sum) | O(1) |