<p>There is a pizza with <code>3n</code> slices of varying size, you and your friends will take slices of pizza as follows:</p>

<ul>
	<li>You will pick <strong>any</strong> pizza slice.</li>
	<li>Your friend Alice will pick the next slice in the anti-clockwise direction of your pick.</li>
	<li>Your friend Bob will pick the next slice in the clockwise direction of your pick.</li>
	<li>Repeat until there are no more slices of pizzas.</li>
</ul>

<p>Given an integer array <code>slices</code> that represent the sizes of the pizza slices in a clockwise direction, return <em>the maximum possible sum of slice sizes that you can pick</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/18/sample_3_1723.png" style="width: 500px; height: 266px;" />
<pre>
<strong>Input:</strong> slices = [1,2,3,4,5,6]
<strong>Output:</strong> 10
<strong>Explanation:</strong> Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively. Then Pick slices with size 6, finally Alice and Bob will pick slice of size 2 and 1 respectively. Total = 4 + 6.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/18/sample_4_1723.png" style="width: 500px; height: 299px;" />
<pre>
<strong>Input:</strong> slices = [8,9,8,6,1,1]
<strong>Output:</strong> 16
<strong>Explanation:</strong> Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.
</pre>

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

<ul>
	<li><code>3 * n == slices.length</code></li>
	<li><code>1 &lt;= slices.length &lt;= 500</code></li>
	<li><code>1 &lt;= slices[i] &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int topdown(int index, int endindex,vector<int>& slices,int n,  vector<vector<int>>&dp){
        if(n == 0 || index > endindex) return 0;
        if(dp[index][n] != -1) return dp[index][n];
        int include = slices[index] + topdown(index+2,endindex,slices,n-1,dp);
        int exclude = 0 + topdown(index+1,endindex,slices,n,dp);
        return dp[index][n] = max(include,exclude);
    }
    int bottomup(vector<int>& slices){
        int k = slices.size();
        vector<vector<int>>dp1(k+2,vector<int>(k+2,0));
        vector<vector<int>>dp2(k+2,vector<int>(k+2,0));
        for(int index = k-2;index >= 0 ;index--){
            for(int n = 1;n<=k/3;n++){
                int include = slices[index] + dp1[index+2][n-1];
                int exclude = 0 + dp1[index+1][n];
                 dp1[index][n] = max(include,exclude);
            }
        }
        int case1 = dp1[0][k/3];
        for(int index = k-1;index >= 1 ;index--){
            for(int n = 1;n<=k/3;n++){
                int include = slices[index] + dp2[index+2][n-1];
                int exclude = 0 + dp2[index+1][n];
                 dp2[index][n] = max(include,exclude);
            }
        }
        int case2 = dp2[1][k/3];
        return max(case1,case2);
    }
    int spaceoptimise(vector<int>& slices){
        int k = slices.size();
        vector<int>prev1(k+2,0);
        vector<int>curr1(k+2,0);
        vector<int>next1(k+2,0);

        vector<int>prev2(k+2,0);
        vector<int>curr2(k+2,0);
        vector<int>next2(k+2,0);
        for(int index = k-2;index >= 0 ;index--){
            for(int n = 1;n<=k/3;n++){
                int include = slices[index] + next1[n-1];
                int exclude = 0 + curr1[n];
                 prev1[n] = max(include,exclude);
            }
            next1 = curr1;
            curr1 = prev1;
        }
        int case1 = curr1[k/3];
        for(int index = k-1;index >= 1 ;index--){
            for(int n = 1;n<=k/3;n++){
                int include = slices[index] + next2[n-1];
                int exclude = 0 + curr2[n];
                 prev2[n] = max(include,exclude);
            }
            next2 = curr2;
            curr2 = prev2;
        }
        int case2 = curr2[k/3];
        return max(case1,case2);
    }
    int maxSizeSlices(vector<int>& slices) {
        // int k = slices.size();
        // vector<vector<int>>dp1(k,vector<int>(k,-1));
        // vector<vector<int>>dp2(k,vector<int>(k,-1));
        // int case1 = topdown(0,k-2,slices,k/3,dp1);
        // int case2 = topdown(1,k-1,slices,k/3,dp2);
        // return max(case1,case2);


        //return bottomup(slices);


        return spaceoptimise(slices);

    }
};
11100