<p>You have <code>k</code> bags. You are given a <strong>0-indexed</strong> integer array <code>weights</code> where <code>weights[i]</code> is the weight of the <code>i<sup>th</sup></code> marble. You are also given the integer <code>k.</code></p>

<p>Divide the marbles into the <code>k</code> bags according to the following rules:</p>

<ul>
	<li>No bag is empty.</li>
	<li>If the <code>i<sup>th</sup></code> marble and <code>j<sup>th</sup></code> marble are in a bag, then all marbles with an index between the <code>i<sup>th</sup></code> and <code>j<sup>th</sup></code> indices should also be in that same bag.</li>
	<li>If a bag consists of all the marbles with an index from <code>i</code> to <code>j</code> inclusively, then the cost of the bag is <code>weights[i] + weights[j]</code>.</li>
</ul>

<p>The <strong>score</strong> after distributing the marbles is the sum of the costs of all the <code>k</code> bags.</p>

<p>Return <em>the <strong>difference</strong> between the <strong>maximum</strong> and <strong>minimum</strong> scores among marble distributions</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> weights = [1,3,5,1], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6. 
The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10. 
Thus, we return their difference 10 - 6 = 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> weights = [1, 3], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> The only distribution possible is [1],[3]. 
Since both the maximal and minimal score are the same, we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= weights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= weights[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
    // int n;
    // long long rec(int i,int parts,vector<vector<long long>> &dp,vector<int> &a){
    //     // base case ;
    //     if(parts==0){
    //         return a[i]+a[n-1];
    //     }
    //     // prune;
    //     if(i >= n-1 && parts > 0){
    //         return 1e18;
    //     }
    //     if(dp[i][parts]!=-1){
    //         return dp[i][parts];
    //     }
    //     long long ans = 1e9;
    //     for(int j=i;j<n-1;j++){
    //        ans = min(ans,a[i]+a[j]+rec(j+1,parts-1,dp,a));
    //     }
    //     return dp[i][parts] = ans;
    // }
    //  long long rec1(int i,int parts,vector<vector<long long>> &dq,vector<int> &a){
    //     // base case ;
    //     if(parts==0){
    //         return a[i]+a[n-1];
    //     }
    //     // prune;
    //     if(i >= n-1 && parts > 0){
    //         return 0;
    //     }
    //     if(dq[i][parts]!=-1){
    //         return dq[i][parts];
    //     }
    //     long long ans = 0;
    //     for(int j=i;j<n-1;j++){
    //        ans = max(ans,a[i]+a[j]+rec1(j+1,parts-1,dq,a));
    //     }
    //     return dq[i][parts] = ans;
    // }
public:
    long long putMarbles(vector<int>& a, int k) {
        int n = a.size();
        for(int i=0;i<n-1;i++){
            a[i]=a[i]+a[i+1];
        }
        a.pop_back();
        long long sum1= 0;
        sort(a.begin(),a.end());
        for(int i=0;i<k-1;i++){
            sum1 += a[i];
        }
        long long sum2=0;
        reverse(a.begin(),a.end());
        for(int i=0;i<k-1;i++){
            sum2 += a[i];
        }
        return sum2-sum1;
    }
};
61500