<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>

void printArr(const vector<int> & a){
    for(int i = 0 ; i < a.size() ; i ++) cout<<a[i]<<" ";
    cout<<endl;
}
void printArr(const vector<vector<int>> & a){
    for(int i = 0 ; i < a.size() ; i ++) printArr(a[i]);
    cout<<endl;
}
class Solution {
public:
    int Helper(const vector<int> & a, int n){
        vector<vector<int>> dp(n, vector<int>(a.size(), 0));
        int i, j;
        for(i = 0 ; i < a.size() ; i ++) dp[0][i] = a[i];
        for(i = 1 ; i < dp[0].size() ; i ++) dp[0][i] = max(dp[0][i], dp[0][i - 1]);
        for(i = 1 ; i < dp.size() ; i ++){
            for(j = 0 ; j < dp[0].size() ; j ++){
                if(j - 2 >= 0) dp[i][j] = a[j] + dp[i - 1][j - 2];
            }
            for(j = 1 ; j < dp[i].size() ; j ++) dp[i][j] = max(dp[i][j],  dp[i][j - 1]);
        }
        int ans = 0;
        for(i = 0 ; i < dp[0].size() ; i ++) ans = max(ans, dp.back()[i]);
        //cout<<"dp:"<<endl;
        //printArr(dp);
        return ans;
    }
    int maxSizeSlices(vector<int>& slices) {
        vector<int> a1, a2;
        int i;
        for(i = 0 ; i < slices.size() - 1 ; i ++){
            a1.push_back(slices[i]);
            a2.push_back(slices[i + 1]);
        }
        int ans1 = Helper(a1, slices.size() / 3);
        int ans2 = Helper(a2, slices.size() / 3);
        return max(ans1, ans2);
    }
};
15900