Split Array Largest Sum

Came up on a Two Sigma loop and was the round I almost botched: I went straight to interval DP, computed the right answer, but ate 35 minutes of the 45-minute slot. The binary-search-on-answer is the version that gets you to a discussion of complexity tradeoffs with time left to talk through it.

Split Array Largest Sum

Given a non-negative integer array nums and an integer k, split nums into k non-empty contiguous subarrays. The cost of a split is the largest sum across the k subarrays. Return the minimum possible cost.

Examples

Example 1:

• Input: nums = [7, 2, 5, 10, 8], k = 2
• Output: 18
• Explanation: The split [7, 2, 5] and [10, 8] has subarray sums 14 and 18, so the max is 18. No 2-way split has a smaller max.

Example 2:

• Input: nums = [1, 2, 3, 4, 5], k = 2
• Output: 9
• Explanation: Split as [1, 2, 3] (sum 6) and [4, 5] (sum 9). Max is 9.

Example 3:

• Input: nums = [1, 4, 4], k = 3
• Output: 4
• Explanation: Three pieces, each must be non-empty: [1], [4], [4]. Max sum is 4.

Example 4:

• Input: nums = [10], k = 1
• Output: 10
• Explanation: Only one possible split.

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Follow-up

The interval-DP solution is O(n^2 * k). The binary-search-on-answer is O(n * log(sum(nums))). For the given constraints both fit, but in interviews the binary-search approach is the version that shows up senior signal because it generalizes to many other problems (Capacity to Ship, Koko Eating Bananas, Painter's Partition).