Given an array of non-negative integers nums and an integer k, cut the array into exactly k non-empty contiguous pieces. Each piece has a sum; the cost of a split is the largest of those sums. Return the smallest cost achievable.
- This is binary search on the answer: search over candidate cost values, not over the array or over the possible cut positions
- Candidate costs run from
max(nums) to sum(nums), and 'can I split within this cost?' is monotone in the cost - Given a cost limit, greedily extend each piece until adding the next value would exceed it, and count how many pieces that takes
k is between 1 and nums.length