Standard LC mediums, nothing too crazy.

Interviewer was pretty chill and was helpful in pointing me in the right direction when I needed as well.

Only thing I would probably change was to study more on graph problems beforehand.

You are given a 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.