Compare the Highest and Lowest Scores from k Contiguous Bags
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Partition all marble weights into exactly k nonempty contiguous groups, preserving their original order. A group from i through j costs weights[i]+weights[j], including twice the value for a singleton. Return the maximum partition score minus the minimum partition score.
```cpp
class Solution {
public:
long long putMarbles(vector<int>& weights, int k);
};
```
### Examples
**Example 1:**
```text
Input: weights = [2,8,1], k = 2
Output: 1
Explanation: Cutting after the first marble scores 13; cutting after the second scores 12.
```
**Example 2:**
```text
Input: weights = [4,7,2], k = 1
Output: 0
Explanation: Only one whole-array group is possible, so maximum and minimum agree.
```
### Constraints
- `1 <= k <= weights.length <= 100000`.
- `1 <= weights[i] <= 10^9`.
### Clarifying Questions
- Must every marble be assigned? Yes, once each.
- Can a bag be empty or skip an interior marble? No; each bag is a nonempty contiguous group.
- What is a singleton bag's cost? Twice its marble's weight.
- What is returned? Maximum total score minus minimum total score.
```hint Check the boundary
Check how the endpoint-cost rule applies to a one-marble bag.
```
Overview: Compare the maximum and minimum scores from exactly k nonempty contiguous marble bags, where each bag costs its two endpoint weights.