<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 dp[1000];

//      int solve(vector<int>& slices,int i,int n, int start, int end){
        
//         if(i>=n){
//             return 0;
//         }
//         if(dp[i]!=-1){
//             return dp[i];
//         }
//         int choose;
//         if((end-i)<=2){
//           choose = slices[i] ;
//         }
//         else{
//             if(start==0){
//               choose = slices[i] + solve(slices, i+2, n, 0, end-1);
//             }
//             else{
//                 choose = slices[i] + solve(slices, i+2, n, start+1, end);
//             }
//         }
//         int notchoose = solve(slices, i+1,n,start + 1,end);

//         return dp[i] = max(choose, notchoose);


//      }
//     int maxSizeSlices(vector<int>& slices) {
//         int n = slices.size();
//         memset(dp,-1,sizeof(dp));
//         return solve(slices,0,n,0,n);
        
//     }
// };


#include <vector>
#include <algorithm>
 

 
int solve(vector<int>& slices, int n, int start, int end) {
    vector<vector<int>> dp(n+1, vector<int>(end-start+2, 0));
    
 
    for (int i = 1; i <= n; i++) {
        for (int j = start; j <= end; j++) {
            if (j-2 >= start) {
                dp[i][j-start+1] = max(dp[i][j-start], dp[i-1][j-start-1] + slices[j]);
            } else {
                dp[i][j-start+1] = max(dp[i][j-start], slices[j]);
            }
        }
    }
    
    return dp[n][end-start+1];
}

int maxSizeSlices(vector<int>& slices) {
    int n = slices.size() / 3;
    
 
    int case1 = solve(slices, n, 0, slices.size()-2);
    
 
    int case2 = solve(slices, n, 1, slices.size()-1);
    
    return max(case1, case2);
}
};
15800