<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:
    def maxSizeSlices(self, slices: List[int]) -> int:
        # brute-force bit manipulation top-down DFS: TLE, clearly, because 2**N is enormous
        
        # then I tried a more clever top-down DFS with 3 dimensions, but it turns out
        # it's wrong because I thought picking the slices we're going to eat in order
        # is equivalent to all other orders.. but it isn't!
        #
        #   example: 9 1 9 1 1 1 1 9 1
        #    If we eat the first two 9s, alice eats 9 and 1 from the back
        #
        # But if we eat the first and third nines, then the last nine is left to us as well.

        # THE CRUCIAL INSIGHT: we can eat any n non-adjacent slices.
        #
        # Most answers make this look obvious, but I didn't think it was obvious at all.
        #
        # Proof:
        #    label the k == N//3 slices we want to eat as 0..k-1
        #      the slices are non-adjacent by assertion, so they're separated by at least one index
        #
        #    the situation we want to avoid is eating the slice labeled 1 first:
        #       0 _ 1 _ 2 _ _ _ _
        #    because if we do, it puts 0 and 2 right next to each other, then when we eat one, alice or bob will eat the other.
        #
        #    to prevent this, we have to eat a slice that is at least TWO away from another slice we want to eat.
        #
        #    Then we're left with
        #       eat 0:     1 _ 2 _ _ _
        #       eat 2: 0 _ 1 _ _ _
        #  If there's at least two unlabled slices to the left or right, then after eating that slice, there will
        #  be at least on slice remaining between others we want to eat.
        #
        # Is there always such a slice?
        #
        # We're eating N//3 of the slices.
        # Suppose there's labeled slice at least two from another slice.
        # Then that would mean every other slice is being eaten by us.
        # But that would mean we're eating N//2 of the slices, not N//3. This is a contradiction.
        # So some of those slices we claimed to have labeled don't, in fact, have a label.
        # This opens up large gaps between slices.

        # This completes the proof: we can pick any non-adjacent N//3 slices because we just showed there's always
        # a strategy for consuming such a collection of chosen slices.

        # suppose we know the best score we can get having eaten s == 0..N//3 slices through indices 0..i-1:
        # then the best we can do through i is
        #     eat i: best[i, s] = slices[i] + best[i-2][s-1]
        #     skip i: best[i, s] = best[i-1][s]

        # this recurrence relation only requires knowing best through the prior two indices so we can optimize space usage

        # TRICKY: houses 0 and N-1 are adjacent so we have to be careful about that; if we consider N-1 when we must NOT have considered 0 earlier
        N = len(slices)
        S = N//3

        # m2 = [-math.inf]*(S+1)
        # m2[0] = 0
        # m1 = m2[:]
        # for i in range(N-1): # 0..N-2, see TRICKY note
        #     curr = [-math.inf]*(S+1)
        #     curr[0] = 0
        #     for s in range(1, S+1):
        #         curr[s] = max(slices[i] + m2[s-1], m1[s]) # s-1 slices through i-2 and i, or s slices through i-1

        #     m2, m1 = m1, curr

        # ans0 = m1[S]

        # m2 = [-math.inf]*(S+1)
        # m2[0] = 0
        # m1 = m2[:]
        # for i in range(1, N): # 1..N-1, see TRICKY note
        #     curr = [-math.inf]*(S+1)
        #     curr[0] = 0
        #     for s in range(1, S+1):
        #         curr[s] = max(slices[i] + m2[s-1], m1[s]) # s-1 slices through i-2 and i, or s slices through i-1

        #     m2, m1 = m1, curr

        # ans1 = m1[S]

        # return max(ans0, ans1)

        # ### Final note: the only difference between the two are the bounds, so let's make a function
        # def solve(lo: int, hi: int) -> int:
        #     m2 = [-math.inf]*(S+1) # best[i-2][:]
        #     m2[0] = 0
        #     m1 = m2[:] # best[i-1][:]
        #     for i in range(lo, hi+1):
        #         curr = [-math.inf]*(S+1)
        #         curr[0] = 0
        #         for s in range(1, S+1):
        #             # ways to have eaten s slices through index i:
        #             #    take s: eat s-1 slices through i-2, then eat i
        #             #    skip s: eat s slices through i-1
        #             curr[s] = max(slices[i] + m2[s-1], m1[s])

        #         m2, m1 = m1, curr

        #     return m1[-1]

        # return max(solve(0, N-2), solve(1, N-1))

        # FINAL FINAL NOTE: I saw another submission that is BRILLIANT.
        #    Note that solve(0, N-2) and solve(1, N-1) are the same if we don't use index 0
        #    We can *guarantee* we don't use index 0 by ROTATING THE ARRAY so index 0 is the min !?
        #    This seems like black magic.
        #    But it kind of makes sense the more I think about it.
        #    The only reason we'd pick the minimum is because we *have* to, because we must pick n slices.
        #    That's after we've exhausted all high elements that aren't adjacent.
        #    We'd have to pick something like  M _ _ M _ _ M _ _ M _ _ M _ _ _ <- last one left... but M _ _ is divis by 3, so fourth isn't possible
        #    In a 6-element case, I found that the only way to be forced to pick the minimum element is if there are multiple copies of the minimum.
        #    In which case we can decide to skip the first copy of the minimum.

        N = len(slices)
        l = min(range(N), key=lambda i: slices[i]) # argmin
        slices = slices[l:] + slices[:l] # rotate array to put first occurrence of min slice value first

        # we'll never pick slice 0 because it's the minimum (see above)
        # so we can iterate through the end; we're free to pick N-1 because we know we didn't pick 0
        m2 = [-math.inf]*(S+1) # best[i-2][:]
        m2[0] = 0
        m1 = m2[:] # best[i-1][:]
        for i in range(1, N):
            curr = [-math.inf]*(S+1)
            curr[0] = 0
            for s in range(1, S+1):
                # ways to have eaten s slices through index i:
                #    take s: eat s-1 slices through i-2, then eat i
                #    skip s: eat s slices through i-1
                curr[s] = max(slices[i] + m2[s-1], m1[s])

            m2, m1 = m1, curr

        return m1[-1]
16500