<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:
        def rob1x(nums,k):
            n = len(nums)
            dp = [[0 for _ in range(k+1)] for _ in range(n)]
            dpx = [[0 for _ in range(k+1)] for _ in range(n)]

            dp[0][1] = nums[0]
            for i in range(1,n):
                for j in range(1,k+1):
                    if j > i:
                        dp[i][j]=0
                    else:
                        dp[i][j] = dpx[i-1][j-1]+nums[i]
                    dpx[i][j] = max(dp[i-1][j], dpx[i-1][j])
                
                    #print(f"dp[{i}][{j}]={dp[i][j]} dpx[{i}][{j}]={dpx[i][j]}")                
            return max(dp[n-1][k],dpx[n-1][k])
        
        nums = slices
        n = len(nums)

        if n <= 3:
            return max(nums)

        # divide the circular structure into two linear structures
        nums2 = nums[2:n-1]
        nums3 = nums[1:n]            
        k = n//3        
        m1 = rob1x(nums2,k-1)+nums[0]   # rob house 0
        m2 = rob1x(nums3,k)             # not rob house 0
        
        return max(m1,m2)






        '''
        def takeLinear(nums,i,j,k):
            n = j-i+1
            if n==1:
                if k==1:
                    print(f"Linear i,j={i,j} n={n} k==1 return nums[i]")
                    return nums[i]
                else:
                    return 0
            elif n==2:
                if k==1:
                    print(f"Linear i,j={i,j} n={n} k==1 return {max(nums[i],nums[i+1])}")                    
                    return max(nums[i],nums[i+1])        
                else:
                    return 0
            elif n==3:
                if k==1:
                    print(f"Linear i,j={i,j} n={n} k==1 return {max(nums[i],nums[i+1],nums[i+2])}")                    
                    return max(nums[i],nums[i+1],nums[i+2])
                elif k==2:
                    print(f"Linear i,j={i,j} n={n} k==2 return {nums[i]+nums[i+2]}")                    
                    return nums[i]+nums[i+2]
                else:
                    return 0

            m1 = takeLinear(nums,i+2,j,k-1)+nums[i]
            m2 = takeLinear(nums,i+1,j,k)
            return max(m1,m2)
        
        def takeLinear(nums,i,j): # take slinces from i to j
            n=len(nums)
            r0=nums[i]  # r: take slice i
            x0=0        # x: not take slice i
            for p in range(i+1,j+1):
                r=x0+nums[p]
                x=max(x0,r0)
                x0,r0 = x, r
            return(max(r0,x0))
        
        def takeCircular(nums,i,j,k):
            n = j-i+1
            if n <= 2:
                if k==1:
                    print(f"i,j={i,j} n={n} k==1 return {max(nums[i],nums[i+1])}")
                    return max(nums[i],nums[i+1])
                else:
                    return 0

            if n == 3:
                if k==1:
                    print(f"i,j={i,j} n={n} k==1 return {max(nums[i:j+1])}")
                    return max(nums[i:j+1])
                elif k==2:
                    print(f"i,j={i,j} n={n} k==2 return {nums[i]+nums[i+2]}")
                    return nums[i]+nums[i+2]
                else:
                    return 0

            # divide the circular structure into two linear structures
            m1 = takeCircular(nums,i+2,j-1,k-1)+nums[i]   # take slice i
            m2 = takeLinear(nums,i+1,j,k)           # not take slice i
        
            return max(m1,m2)


        n = len(slices)
        k = n//3
        return takeCircular(slices,0,n-1,k)

        #---------------------------------------------------
        n = len(slices)
        dp00 = [0 for _ in range(n)]
        dp01 = [0 for _ in range(n)]
        dp10 = [0 for _ in range(n)]
        dp11 = [0 for _ in range(n)]

        dp00[0],dp01[0],dp10[0],dp11[0] = 0,0,0,slices[0]
        dp00[1],dp01[1],dp10[1],dp11[1] = 0,slices[1],slices[0],0
        for i in range(2,n):
            dp00[i] = max(dp00[i-1],dp01[i-1])
            dp01[i] = dp00[i-1]+slices[i]
            
            dp10[i] = max(dp10[i-1],dp11[i-1])
            dp11[i] = dp10[i-1]+slices[i]
            
            print(f"dp00[{i}]={dp00[i]},dp01[{i}]={dp01[i]},dp10[{i}]={dp10[i]},dp11[{i}]={dp11[i]}")
        #dp00[n-1] = max(dp00[i-1],dp01[i-1])
        #dp01[n-1] = dp00[i-1]+slices[i]
        #dp10[n-1] = max(dp10[i-1],dp11[i-1])
        
        #dp11[n-1] = 0
        
        return max(dp00[n-1],dp01[n-1],dp10[n-1])
        '''
19000