Modified Binary Search
LC #410Hard
Split Array Largest Sum
Modified Binary Search
GoogleMetaAmazonBloombergProblem
Split an array into k non-empty subarrays to minimize the largest subarray sum.
binary-searchgreedydynamic-programming
Constraints
- ›1 ≤ nums.length ≤ 1000
- ›0 ≤ nums[i] ≤ 10⁶
- ›1 ≤ k ≤ min(50, nums.length)
Example
Input
nums = [7, 2, 5, 10, 8], k = 2Output
18Why
Split into [7,2,5] and [10,8] → max sum 18. Or [7,2,5,10] and [8] → 24. Best is 18.