Problem: Put Marbles in Bags

Difficulty: Hard

Problem Statement :

You have k bags and are given a 0-indexed integer array weights where weights[i] represents the weight of the iᵗʰ marble. Your task is to divide the marbles into the k bags following these rules:

1. No bag is empty.
2. Contiguous Assignment: If the iᵗʰ and jᵗʰ marbles are in a bag, then all marbles with indices between i and j must also be in that bag.
3. Bag Cost: If a bag contains marbles from index i to j inclusively, its cost is calculated as weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all k bags.

Objective: Return the difference between the maximum and minimum scores achievable through different valid distributions of the marbles.

Examples

Example 1:

Input:

weights = [1,3,5,1], k = 2

Output:

4

Explanation:

• Minimal score distribution: [1], [3,5,1] → (1+1) + (3+1) = 6
• Maximal score distribution: [1,3], [5,1] → (1+3) + (5+1) = 10 Difference: 10 - 6 = 4

Input:

weights = [1, 3], k = 2

Output:

0

Explanation:

• The only possible distribution is [1], [3], resulting in the same score for both maximum and minimum.