Show problems as
Classic problem #2551HardArrayGreedySortingHeap (Priority Queue)

Put Marbles in Bags

Real-world version: Splitting a Line of Marbles Into Bags
Tracked in this browser only
Read Put Marbles in Bags on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Marbles stand in a line with weights weights. They are put into exactly k bags so that every bag holds a run of neighbouring marbles, no bag is empty, and every marble goes into a bag.

A bag's cost is the weight of its first marble plus the weight of its last. The score of a way of bagging is the total of its bags' costs.

Return the difference between the largest and the smallest score any bagging can have.

Examples

Example 1

Input
weights = [14, 3, 27, 9, 41, 6], k = 3
Output
50

Two cuts are placed among the five neighbouring pairs, whose totals are 17, 30, 36, 50 and 47. The largest score takes the two heaviest, 50 and 47, and the smallest takes 17 and 30, so the difference is 50.

Example 2

Input
weights = [5, 9], k = 2
Output
0

There is only one place to cut, so every bagging scores the same.

Example 3

Input
weights = [5], k = 1
Output
0

A single bag needs no cuts at all.

Constraints

  • 1 <= weights.length <= 10^5
  • 1 <= k <= weights.length
  • 1 <= weights[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def put_marbles(weights: list[int], k: int) -> int:
Java
public long putMarbles(int[] weights, int k)

More on the same topics