<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 solve(int index,int endIndex ,vector<int>&slices,int n){
    if(n==0 || index>endIndex){
        return 0;
    }
  int take=slices[index]+solve(index+2,endIndex,slices,n-1);
  int notTake=0+solve(index +1,endIndex,slices,n);
  return max(take,notTake);   

 }
  int solveMemo(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 take = slices[index] + solveMemo(index + 2, endIndex, slices, n - 1, dp);
        int notTake = 0 + solveMemo(index + 1, endIndex, slices, n, dp);

        return dp[index][n] = max(take, notTake);
    }

      int solveTabulation(int startIndex, int endIndex, vector<int>& slices, int n) {
        int length = endIndex - startIndex + 1;
        vector<vector<int>> dp(length + 1, vector<int>(n + 1, 0));

        for (int index = length - 1; index >= 0; index--) {
            for (int remaining = 1; remaining <= n; remaining++) {
                int take = slices[startIndex + index] + (index + 2 <= length - 1 ? dp[index + 2][remaining - 1] : 0);
                int notTake = dp[index + 1][remaining];
                dp[index][remaining] = max(take, notTake);
            }
        }
        return dp[0][n];
    }
    int maxSizeSlices(vector<int>& slices) {

       /* Recursion 
        int k=slices.size();
        int case1=solve(0,k-2,slices,k/3);
        int case2=solve(1,k-1,slices,k/3);
        */
          int k = slices.size();
        
        // Memoization 
      /*  vector<vector<int>>dp1(k,vector<int>(k /3 + 1,-1));
        vector<vector<int>>dp2(k,vector<int>(k /3 + 1,-1));
        int case1 = solveMemo(0, k - 2, slices, k / 3, dp1);
        int case2 = solveMemo(1, k - 1, slices, k / 3, dp2);
       */
         int case1 = solveTabulation(0, k - 2, slices, k / 3);
        int case2 = solveTabulation(1, k-1, slices, k/3);
        return max(case1, case2);
    }
};
16700