Put Marbles in Bags
You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the i^th marble. You are also given the integer k.
Divide the marbles into the k bags according to the following rules:
- No bag is empty.
- If the
i^thmarble andj^thmarble are in a bag, then all marbles with an index between thei^thandj^thindices should also be in that same bag. - If a bag consists of all the marbles with an index from
itojinclusively, then the cost of the bag isweights[i] + weights[j].
The score after distributing the marbles is the sum of the costs of all the k bags.
Return the difference between the maximum and minimum scores among marble distributions.
Example 1
Input
weights = [1,3,5,1], k = 2Output
4The minimal score is 6 from [1],[3,5,1], and the maximal score is 10 from [1,3],[5,1], so the difference is 4.
Example 2
Input
weights = [1,3], k = 2Output
0The only distribution possible is [1],[3], so the maximum and minimum scores are the same.
Constraints
- 1 <= k <= weights.length <= 10^5
- 1 <= weights[i] <= 10^9