962. Marble Bag Spread
A shopkeeper has marbles in a row, weights[i] being the weight of marble i (0-indexed), and must place them into exactly k bags. Each bag takes a non-empty contiguous block of the row, and every marble goes in one bag, in order. The price of a bag covering marbles i..j is weights[i] + weights[j] (for a single marble that is twice its weight), and the total score of a split is the sum of its bag prices.
Return the largest possible total score minus the smallest possible total score over all valid splits into k bags.
Example 1
- Input:
- weights = [4,1,7,2,9], k = 3
- Output:
- 7
- Explanation:
Adjacent pair sums are 5, 8, 9, 11; splitting at the two largest cuts gives extra 20, at the two smallest 13, difference 7.
Example 2
- Input:
- weights = [5,6,7], k = 1
- Output:
- 0
- Explanation:
With a single bag every split is the same, so the spread is 0.
Example 3
- Input:
- weights = [3,3,3,3], k = 4
- Output:
- 0
- Explanation:
Each marble is its own bag, so there is only one way to split and the spread is 0.
Constraints
- 1 ≤ k ≤ weights.length ≤ 105
- 1 ≤ weights[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)