Marbles Into Bags
weights lists the marbles lying in a row. Split the row into exactly k bags: every bag takes a stretch of neighboring marbles, no bag is empty, and every marble goes into a bag.
A bag costs the weight of its first marble plus the weight of its last marble; a bag with a single marble counts that marble twice. The score of a split is the total cost of its bags.
Return the largest possible score minus the smallest possible score.
Example 1
Bags [2] and [6, 1, 4] score 2 + 2 + 6 + 4 = 14. Bags [2, 6, 1] and [4] score 2 + 1 + 4 + 4 = 11. No split scores more than 14 or less than 11.
Example 2
Three marbles into three bags: there is only one way, so both scores are equal.
Example 3
One bag has to take the whole row.
Constraints
1 <= k <= len(weights) <= 301 <= weights[i] <= 10**9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Most Workshops Before Their DeadlinesHard
- Narrowest SpreadHard
- Saw, Then PaintHard
- Seat the Pairs TogetherHard
- Two From Every IntervalHard
- Coins Handed BackBeginner
- Coins on the TableBeginner
- Fewest BanknotesBeginner