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

// https://www.youtube.com/watch?v=Pkip_mJhiFk
// https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/1388.Pizza-With-3n-Slices


// dp_rob[i][k]: the maximum gain by the i-th round if we take k slices, and for the i-th slice we do take it.
// dp_norob[i][k]: the maximum gain by the i-th round if we take k slices, and for the i-th slice we do NOT take it.

// class Solution {
// public:
//     int maxSizeSlices(vector<int>& slices)
//     {
//         int n = slices.size();
//         return max(helper(0, n-2, n/3, slices), helper(1, n-1, n/3, slices));
//     }
//     int helper(int start, int end, int k, vector<int>& slices)
//     {
//         auto dp0 = vector<vector<int>>(501, vector<int>(501, 0));
//         auto dp1 = vector<vector<int>>(501, vector<int>(501, 0));

//         dp0[start][0] = 0;
//         dp1[start][1] = slices[start];
        
//         for (int i=start+1; i<=end; i++)
//             for (int j=1; j<=min(k, i-start+1); j++)
//             {
//                 dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j]);
//                 dp1[i][j] = dp0[i-1][j-1] + slices[i];
//             }
//         return max(dp0[end][k], dp1[end][k]);

//     }
// };



// https://github.com/wisdompeak/LeetCode/blob/master/Dynamic_Programming/1388.Pizza-With-3n-Slices/1388.Pizza-With-3n-Slices.cpp
class Solution
{
public:
    int maxSizeSlices(vector<int>& slices)
    {
        int n = slices.size();
        return max(helper(0, n-2, n/3, slices), helper(1, n-1, n/3, slices));
    }

    int helper(int start, int end, int K, vector<int>& slices)
    {
        auto dp_norob = vector<int>(K+1, 0);
        auto dp_rob = vector<int>(K+1, 0);
        
        // for (int i=start; i<=end; i++)
            // for (int k=min(K, i-start+1); k>=1; k--)
        for (int i=start; i<=end; i++)
            for (int k=min(K, i-start+1); k>=1; k--)
            {
                dp_norob[k] = max(dp_norob[k], dp_rob[k]);
                dp_rob[k] = slices[i] + dp_norob[k-1];
            }
        return max(dp_rob[K], dp_norob[K]);
    }
};

10600