Approach Summary
Binary search on the answer (largest sum). Feasibility: count how many partitions are needed with given max sum — must be ≤ k.
How to Recognize This Pattern
- "Minimise the maximum subarray sum" with k splits
- Monotonic feasibility → binary search on answer
Complexity Analysis
Time Complexity
O(n log(sum))
Space Complexity
O(1)
Tags
Array Binary Search Dynamic Programming