<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 dfs(int i, int n, std::vector<int> &slices)
    {
        auto m = slices.size();
        if (3 * n == m)
        {
            return 3 * n == m ? 0 : INT_MIN;
        }
        int maxSum = 0;

        if (m_memo[i][n] != -1)
        {
            return m_memo[i][n];
        }

        // pick slice i
        if (i + 2 <= m)
        {
            maxSum = std::max(maxSum, slices[i] + dfs(i + 2, n + 1, slices));
        }

        // don't pick slice i
        if (i + 1 <= m)
        {
            maxSum = std::max(maxSum, dfs(i + 1, n, slices));
        }
        return m_memo[i][n] = maxSum;
    }

    int maxSizeSlices(std::vector<int> &slices)
    {
        auto n = slices.size();
        std::memset(m_memo, -1, 500 * 167 * sizeof(int));
        auto max1 = dfs(0, 0, slices);
        std::memset(m_memo, -1, 500 * 167 * sizeof(int));
        std::rotate(std::begin(slices), std::begin(slices) + 1, std::end(slices));
        auto max2 = dfs(0, 0, slices);

        return std::max(max1, max2);
    }
    int m_memo[500][167];
};
10700