Split Array Largest Sum

Problem

You are given an array of non-negative integers nums and an integer k. Split the array into k contiguous, non-empty subarrays. Each split has a "cost" equal to the largest subarray sum it produces. Return the minimum possible cost over all valid splits.

• nums has between 1 and 5,000 elements, each between 0 and 1,000,000.
• k is between 1 and the length of nums, so a split always exists.

Examples

• nums = [4, 9, 3, 6, 11, 2], k = 3 → 13. Split as [4, 9], [3, 6], [11, 2]; the largest sum is 13, and no three-way split does better because 11 must share a piece with at least one neighbour or leave 9 and 4 together.
• nums = [5, 1, 8, 2, 7], k = 2 → 14. [5, 1, 8] and [2, 7] give sums 14 and 9; cutting one position earlier gives 6 and 17.
• nums = [6, 3, 9], k = 3 → 9. Every element becomes its own piece; the answer is simply the maximum.

Hints

1. Instead of asking "what is the best split?", ask "can I split into at most k pieces so that no piece exceeds a budget B?" How would you check that for a fixed B?
2. If a budget B is achievable, is every larger budget also achievable? What does that let you do with B?
3. Binary search on the budget between max(nums) and sum(nums); the feasibility check is a greedy pass that starts a new piece whenever adding the next element would exceed B.