Split into k pieces

hardBinary searchGreedy choice target 40 min

Split into k pieces

Not solved yetLeetCode 410. Split Array Largest Sum

You get a list nums of non-negative integers and a whole number k. Cut the list into exactly k pieces. Each piece is a run of neighboring items with at least one item in it, and every item lands in exactly one piece, so the pieces keep the list's order. The sum of a piece is the total of its items.

Every way of cutting has a largest piece sum. Return the smallest largest piece sum that any way of cutting can reach.

Picture nums as jobs waiting in a queue and k as workers who each take a run of jobs in order: you want the busiest worker to have as little work as possible.

Example 1

Inputnums = [3, 1, 4, 1, 5], k = 2Output8

Cut after the 4: [3, 1, 4] sums to 8 and [1, 5] to 6. The other three cuts give largest sums 11, 10 and 9.

Example 2

Inputnums = [6, 1, 1, 1, 1], k = 3Output6

[6], [1, 1], [1, 1]. The 6 sits in some piece, so no cut can do better than 6.

Example 3

Inputnums = [7, 2, 5], k = 1Output14

One piece holds everything: 7 + 2 + 5 = 14.

Constraints

1 ≤ len(nums) ≤ 1,000
0 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ min(50, len(nums))

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern