You have a row of marbles, where weights[i] is the weight of marble i, and k bags. Put all the marbles into the bags so that:
- No bag is empty.
- Each bag holds a contiguous stretch of the row: if marbles
iandjshare a bag, every marble between them is in that bag too.
A bag holding marbles i through j costs weights[i] + weights[j] — its first marble plus its last (a bag with a single marble counts that marble twice). The score of a distribution is the total cost of all k bags.
Return the difference between the maximum and the minimum score over all possible distributions.
The answer can be larger than 2^31 − 1, so use a 64-bit integer (
long/long long) in Java, C++ and C.
Examples
Example 1
Input: weights = [1,4,2,5,2], k = 3
Output: 3
The highest score comes from [1,4,2] [5] [2]: (1+2) + (5+5) + (2+2) = 17. The lowest comes from [1] [4] [2,5,2]: (1+1) + (4+4) + (2+2) = 14. 17 − 14 = 3.
Example 2
Input: weights = [10,1,1,10], k = 2
Output: 9
[10] [1,1,10] scores (10+10) + (1+10) = 31, while [10,1] [1,10] scores (10+1) + (1+10) = 22.
Example 3
Input: weights = [1,3], k = 2
Output: 0
There's only one way to split two marbles into two bags, so the maximum and minimum are equal.
Example 4
Input: weights = [7], k = 1
Output: 0
Example 5
Input: weights = [1,2,3,4,5], k = 3
Output: 8
Constraints
1 <= k <= weights.length <= 10^51 <= weights[i] <= 10^9