FunctionRacerProblemsRace

Marbles Into Bags

HardGreedyPython, JavaScript, TypeScript, Java, C++

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

weights [2,6,1,4]
k 2
returns 3

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

weights [5,5,5]
k 3
returns 0

Three marbles into three bags: there is only one way, so both scores are equal.

Example 3

weights [1,9,1,9,1]
k 1
returns 0

One bag has to take the whole row.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems