338. Split Array Largest Sum
You are given an array of non-negative integers nums and an integer k. Cut the array into exactly k non-empty contiguous pieces — no reordering, every element lands in exactly one piece, and the pieces cover the array left to right.
Every piece has a sum, and the cost of a particular split is the largest of those piece sums. Different splits have different costs; return the smallest cost achievable over all valid ways to make the k cuts.
The answer is a single integer.
Example 1:
Input: nums = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: Cutting after the 5 gives pieces [7, 2, 5] and [10, 8] with sums 14 and 18, so the cost is 18. Every other single cut produces a piece summing to more than 18.
Example 2:
Input: nums = [1, 2, 3, 4, 5], k = 2
Output: 9
Explanation: The split [1, 2, 3] | [4, 5] has piece sums 6 and 9. No two-piece split does better than 9.
Example 3:
Input: nums = [1, 4, 4], k = 3
Output: 4
Explanation: With three pieces each element stands alone: sums 1, 4, 4, so the largest is 4.
Constraints:
- 1 ≤ nums.length ≤ 1000
- 0 ≤ nums[i] ≤ 10⁶
- 1 ≤ k ≤ min(50, nums.length)
Hints:
Flip the question. Instead of "what is the best split into k pieces?", ask "given a budget cap on piece sums, how few pieces do I need?" That check is a single greedy left-to-right scan.
The check is monotone: if a cap is achievable with at most k pieces, every larger cap is too. A monotone yes/no over a numeric range is exactly what binary search on the answer solves — search between max(nums) and sum(nums).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [7, 2, 5, 10, 8], k = 2
Expected output: 18