Amazon Software Development Engineer (SDE) Intern interview questions

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.