Put Marbles in Bags

You are given an 0-indexed integer array weights, where weights[i] represents the weight of the i-th marble, and an integer k.

Your task is to divide the marbles into k bags such that:

• No bag is empty.
• Each bag must contain marbles from a contiguous range of indices. That is, if a bag includes marbles at indices i and j, then all marbles with indices between i and j (inclusive) must also be included in that same bag.
• The cost of a bag that includes marbles from index i to j (inclusive) is defined as weights[i] + weights[j].

The total score of a distribution is the sum of the costs of all k bags.

Return the difference between the maximum and minimum possible scores among all valid distributions.

Example 1:

Input: weights = [5,7,9,5], k = 2

Output: 4

Explanation:
The distribution [5,7],[9,5] results in maximal score of (5 + 7) + (9 + 5) = 26.
The distribution [5],[7,9,5] results in minimal score of (5 + 5) + (7 + 5) = 22.
The difference between maximum and minimum scores is 4.

Example 2:

Input: weights = [1,4,2,5,2], k = 3

Output: 3

Explanation:
The distribution [1,4,2],[5],[2] results in maximal score of (1 + 2) + (5 + 5) + (2 + 2) = 17.
The distribution [1],[4],[2,5,2] results in minimal score of (1 + 1) + (4 + 4) + (2 + 2) = 14.
The difference between maximum and minimum scores is 3.

Constraints:

• 1 <= k <= weights.length <= 100,000
• 1 <= weights[i] <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.