#2551
Put Marbles in Bags
specialist · 965 · lc hard +32 · verified · 72.2% accepted · 2,647 likes · top 81%
Description
You have a 0-indexed weights array of marble weights and must fill k non-empty bags with contiguous groups of marbles. Each bag covering indices i to j incurs cost weights[i] + weights[j]. The distribution score is the total cost across all bags. Return the difference between the maximum and minimum achievable scores.
Example 1:
Input: weights = [1,3,5,1], k = 2
Output: 4
Explanation:
The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6.
The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10.
Thus, we return their difference 10 - 6 = 4.
Example 2:
Input: weights = [1, 3], k = 2
Output: 0
Explanation: The only distribution possible is [1],[3].
Since both the maximal and minimal score are the same, we return 0.
Code
1
2
3