There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:

You will pick any pizza slice.
Your friend Alice will pick next slice in anti clockwise direction of your pick. 
Your friend Bob will pick next slice in clockwise direction of your pick.
Repeat until there are no more slices of pizzas.

Sizes of Pizza slices is represented by circular array slices in clockwise direction.
Return the maximum possible sum of slice sizes which you can have.
 
Example 1:

Input: slices = [1,2,3,4,5,6]
Output: 10
Explanation: 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.

Example 2:

Input: slices = [8,9,8,6,1,1]
Output: 16
Output: Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.

Example 3:
Input: slices = [4,1,2,5,8,3,1,9,7]
Output: 21

Example 4:
Input: slices = [3,1,2]
Output: 3

 
Constraints:

1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000

Difficulty: interview

Starter code:

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        

Solutions:
class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        a,b,n=[slices[0]],[0],len(slices)
        for i in range(1,n):
            a.append(max(a[-1],slices[i]))
            b.append(max(b[-1],slices[i]))
        for i in range(2,2*n//3,2):
            aa,bb=[0]*(n-1),[0]*n
            for j in range(i,n-1): aa[j]=max(aa[j-1],a[j-2]+slices[j])
            for j in range(i+1,n): bb[j]=max(bb[j-1],b[j-2]+slices[j])
            a,b=aa,bb
        return max(a[-1],b[-1])

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        rounds = n//3
        
        def num_s(slices):
            # print(slices)
            n = len(slices)
            dp = [i for i in slices]
            for i in range(rounds):
                maxx = 0
                dp2 = [0]*(i*2)
                for j in range(i*2,n):
                    # print(j)
                    if i == 0:
                        dp2.append(max(maxx,slices[j]))
                        maxx = dp2[j]
                    else:
                        dp2.append(max(maxx,slices[j] + dp[j-2]))
                        maxx = dp2[j]
                dp = dp2     
                # print(dp, slices)
            return dp[len(dp)-1]
        
        return max(num_s(slices[1:]),num_s(slices[:n-1]))

            
            

        


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        @lru_cache(None)
        def dp(i, k):
            if k == 0 or i > j:
                return 0
            return max(dp(i + 1, j, k), slices[i] + dp(i + 2, j, k - 1))
        n = len(slices)
        k = n // 3
        dp = collections.deque([[0] * (k + 1) for i in range(2)])
        for i in range(n - 2, -1, -1):
            new_dp = [0] * (k + 1)
            for j in range(1, k + 1):
                new_dp[j] = max(dp[0][j], slices[i] + dp[1][j - 1])
            dp.pop()
            dp.appendleft(new_dp)
        a = dp[0][k]
        dp.clear()
        dp.extend([[0] * (k + 1) for i in range(2)])
        for i in range(n - 1, 0, -1):
            new_dp = [0] * (k + 1)
            for j in range(1, k + 1):
                new_dp[j] = max(dp[0][j], slices[i] + dp[1][j - 1])
            dp.pop()
            dp.appendleft(new_dp)
        b = dp[0][k]
        return max(a, b)

from functools import lru_cache

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3

        results = [0, 0]
        for offset in range(2):
            cur = [0] * n
            prev = [0] * n
            for i in range(1, k + 1):
                cur[1] = w[offset]
                for j in range(2, n):
                    cur[j] = max(prev[j - 2] + w[j - 1 + offset], cur[j - 1])
                prev = cur
                cur = [0] * n
            results[offset] = prev[-1]

        return max(results)

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        k = n // 3
        dp1 = collections.deque([[0] * (k + 1) for i in range(2)])
        dp2 = collections.deque([[0] * (k + 1) for i in range(2)])
        for i in range(n - 2, -1, -1):
            new_dp1 = [0] * (k + 1)
            new_dp2 = [0] * (k + 1)
            for j in range(1, k + 1):
                new_dp1[j] = max(dp1[0][j], slices[i] + dp1[1][j - 1])
                new_dp2[j] = max(dp2[0][j], slices[i + 1] + dp2[1][j - 1])
            dp1.pop()
            dp1.appendleft(new_dp1)
            dp2.pop()
            dp2.appendleft(new_dp2)
        return max(dp1[0][k], dp2[0][k])


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices) // 3
        def linear(arr):
            # index = nb slices eaten.
            a = [0] * (n+1)  # Two slices ago.
            b = [0] * (n+1)  # Previous slice.
            for x in arr:
                a, b = b, [i and max(x + a[i-1], b[i]) for i in range(n+1)]
                # print(a,b)
            return b[-1]
        return max(linear(slices[1:]), linear(slices[:-1]))


from functools import lru_cache

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3

        results = [0, 0]
        for offset in range(2):
            cur = [0] * n
            prev = [0] * n
            for i in range(1, k + 1):
                cur[1] = w[offset]
                for j in range(2, n):
                    cur[j] = max(prev[j - 2] + w[j - 1 + offset], cur[j - 1])
                prev[:] = cur
                cur[:] = [0] * n
            results[offset] = prev[-1]

        return max(results)

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices) // 3
        def max_adj_sum(a):
            l = len(a)
            if l == 0:
                return 0
            if l == 1:
                return a[0]
            dp = [[0] * l for i in range(n + 1)]
            for i in range(1, n + 1):
                dp[i][0] = a[0]
                for j in range(1, l):
                    t = dp[i - 1][j - 2] if j >= 2 else 0
                    dp[i][j] = max(dp[i][j - 1], a[j] + t)
            #print(dp)
            return dp[n][-1]
        #print(max_adj_sum(slices[1:]))
        return max(max_adj_sum(slices[1:]), max_adj_sum(slices[:-1]))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        ## hard
        m = len(slices)
        n = m // 3
        dp = [[0]*(n+1) for i in range(m+1)]
        for i in range(m-2, -1, -1):
            for j in range(1, n+1):
                dp[i][j] = max(dp[i+1][j], slices[i]+dp[i+2][j-1])
        #print(dp[0][n])
        dp2 = [[0]*(n+1) for i in range(m+2)]
        for i in range(m-1, 0, -1):
            for j in range(1, n+1):
                dp2[i][j] = max(dp2[i+1][j], slices[i]+dp2[i+2][j-1])
                
        return max(dp[0][n], dp2[1][n])


class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        k = len(w)//3
        
        #last element is excluded
        dp1 = [[0]*(len(w)) for _ in range(k+1)]
        #first element is excluded
        dp2 = [[0]*(len(w)) for _ in range(k+1)]
        
        for n in range(1,k+1):
            for i in range(1,len(w)):
                
                if i==1:
                    dp1[n][i] = w[i-1]
                    dp2[n][i] = w[i]
                    continue
                
                dp1[n][i] = max(dp1[n-1][i-2]+w[i-1],dp1[n][i-1])
                dp2[n][i] = max(dp2[n-1][i-2]+w[i],dp2[n][i-1])
        return max(dp1[-1][-1],dp2[-1][-1])

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n=len(slices)
        idx = min(range(n), key=lambda x: slices[x])
        slices = slices[idx+1:] + slices[:idx]
        @lru_cache(None)
        def dp(i,k):
            if i>=n-1 or k==0:
                return 0
            return max(slices[i]+dp(i+2,k-1),dp(i+1,k))
        return dp(0,n//3)

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        m = len(slices)
        n = m // 3
        slice1 = slices[:m - 1]
        slice2 = slices[1:]
        return max(self.max_sum(slice1, n), self.max_sum(slice2, n))

    def max_sum(self, slices, n):
        m = len(slices)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if i == 1:
                    dp[i][j] = slices[0]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i - 1])
        return dp[m][n]

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        k = len(w)//3
        
        #last element is excluded
        dp1 = [[0]*(len(w)) for _ in range(k+1)]
        #first element is excluded
        dp2 = [[0]*(len(w)) for _ in range(k+1)]
        
        for n in range(1,k+1):
            for i in range(1,len(w)):
                if i==1:
                    dp1[n][i]=w[0]
                    dp2[n][i]=w[1]
                    continue
                
                dp1[n][i] = max(dp1[n-1][i-2]+w[i-1],dp1[n][i-1])
                dp2[n][i] = max(dp2[n-1][i-2]+w[i],dp2[n][i-1])
        return max(dp1[k][-1],dp2[k][-1])                
        


from functools import lru_cache

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3
        dp1 = [[0] * n for _ in range(k + 1)]

        for i in range(1, k + 1):
            dp1[i][1] = w[0]
            for j in range(2, n):
                dp1[i][j] = max(dp1[i - 1][j - 2] + w[j - 1], dp1[i][j - 1])

        r1 = dp1[-1][-1]

        for i in range(1, k + 1):
            dp1[i][1] = w[1]
            for j in range(2, n):
                dp1[i][j] = max(dp1[i - 1][j - 2] + w[j], dp1[i][j - 1])

        return max(dp1[-1][-1], r1)

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        self.slices = slices
        n = len(self.slices)
        self.mem = dict()
        rv1 = self.dfs(1, n-1, n//3)
        rv2 = self.dfs(0, n-2, n//3)
        return max(rv1, rv2)
        
        
    def dfs(self, i, j, k):
        if k <= 0:
            return 0
        if j - i + 1 < 2*k-1:
            return -float('inf')
        key = (i,j,k)
        if key in self.mem:
            return self.mem[key]
        rv = max(self.dfs(i+1, j, k), self.slices[i] + self.dfs(i+2, j, k-1))
        self.mem[key] = rv
        return rv

class Solution:
    
    def __init__(self):
        self.dp = {}
    
    def solve_linear(self, slices, ind, to_choose):
        if (ind, to_choose) not in self.dp:
            N = len(slices)
            if N <= ind or to_choose == 0:
                return 0
            result_choose = self.solve_linear(slices, ind + 2, to_choose - 1)
            result_not_choose = self.solve_linear(slices, ind + 1, to_choose)
            self.dp[(ind, to_choose)] = max(result_choose + slices[ind], result_not_choose)
        return self.dp[(ind, to_choose)]
    
    def maxSizeSlices(self, slices: List[int]) -> int:
        min_elem = min(slices)
        min_ind = 0
        while slices[min_ind] != min_elem:
            min_ind += 1
        N = len(slices)
        min_ind += 1
        arr = [0 for _ in range(N)]
        for i in range(N):
            arr[i] = slices[(min_ind + i) % N]
        return self.solve_linear(arr, 0, int(N/3))


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        def helper(start, end):
            dp = [[0] * n for _ in range(end-start+1)]
            dp[0] = [slices[start]] * n
            dp[1] = [max(slices[start], slices[start+1])] * n
            for i in range(start+2, end+1):
                dp[i-start][0] = max(slices[i], dp[i-start-1][0])
                for j in range(1, n):
                    dp[i-start][j] = max(dp[i-start-1][j], slices[i] + dp[i-start-2][j-1])
            return dp[-1][-1]
        
        n = len(slices) // 3
        return max(helper(0, len(slices) - 2), helper(1, len(slices) - 1))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        k = len(slices) // 3

        dp1 = [[0] * len(slices) for _ in range(k + 1)]
        dp2 = [[0] * len(slices) for _ in range(k + 1)]
        
        for i in range(1, k + 1):
            for j in range(1, len(slices)):
                if j == 1:
                    dp1[i][j] = slices[j - 1]
                    dp2[i][j] = slices[j]
                else:
                    dp1[i][j] = max(dp1[i - 1][j - 2] + slices[j - 1], dp1[i][j - 1])
                    dp2[i][j] = max(dp2[i - 1][j - 2] + slices[j], dp2[i][j - 1])
        return max(dp1[-1][-1], dp2[-1][-1])

# class LinkedNode:
#     def __init__(self, val):
#         self.val = val
#         self.next = None
#         self.prev = None

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        
        slicesN = len(slices)
        target = slicesN//3
        
        table1 = [[0 for i in range(slicesN)] for ti in range(target+1)]
        table2 = [[0 for i in range(slicesN)] for ti in range(target+1)]
        
        
        for ti in range(1, target + 1):
            for i in range(1, slicesN):
                if i == 1:
                    table1[ti][i] = slices[i]
                    table2[ti][i] = slices[i-1]
                    continue
                table1[ti][i] = max(table1[ti][i-1], table1[ti-1][i-2] + slices[i])
                table2[ti][i] = max(table2[ti][i-1], table2[ti-1][i-2] + slices[i-1])
        
        return max(table1[-1][-1], table2[-1][-1])
    
#         slicesN = len(slices)
#         table = [[] for _ in range(slicesN)]
#         target = slicesN//3
        
#         table[-1] = [slices[-1]]
#         table[-2] = [slices[-2]]
#         table[-3] = [slices[-3], slices[-3]+slices[-1]]
        
#         table2 = [[] for _ in range(slicesN)]

#         table2[-1] = [slices[-1]]
#         table2[-2] = [slices[-2]]
#         table2[-3] = [slices[-3]]
        
#         for i in range(slicesN-4, -1, -1):
#             table[i].append(slices[i])
#             table2[i].append(slices[i])
#             for j in range(i+2, slicesN):
#                 for k, sumTemp in enumerate(table[j]):
#                     if k+1 > target:
#                         break
#                     if k+1 >= len(table[i]):
#                         table[i].append(sumTemp + slices[i])
#                     else:
#                         table[i][k+1] = max(table[i][k+1], sumTemp + slices[i])
#                 for k, sumTemp in enumerate(table2[j]):
#                     if k+1 > target:
#                         break
#                     if k+1 >= len(table2[i]):
#                         table2[i].append(sumTemp + slices[i])
#                     else:
#                         table2[i][k+1] = max(table2[i][k+1], sumTemp + slices[i])   
#         target = slicesN//3
#         ans1 = 0
#         for i, sums in enumerate(table[1:]):
#             if len(sums) >= target:
#                 ans1 = max(ans1, sums[target-1])
         
#         ans2 = 0
#         for i, sums in enumerate(table2):
#             if len(sums) >= target:
#                 ans2 = max(ans2, sums[target-1])
#         return max(ans1, ans2)

            
        
#         @lru_cache
#         def takePizza(slices0):
#             # print(slices0)
#             n = len(slices0)
#             if n == 3:
#                 return max(slices0)
#             subAns = max(slices0[0] + takePizza(slices0[2:n-1]), slices0[n-1] + takePizza(slices0[1:n-2]))
#             for i in range(1, n-1):
#                 subAns = max(subAns, slices0[i] + takePizza(slices0[:i-1] + slices0[i+2:]))
#             return subAns

#         return takePizza(tuple(slices))
        
#         pointerDict = {}
#         head = LinkedNode(0)
#         preNode = head
        
#         for i, pizzaSlice in enumerate(slices):
#             newLN = LinkedNode(pizzaSlice)
#             pointerDict[newLN] = i
#             preNode.next = newLN
#             newLN.prev = preNode
#             preNode = newLN
            
#         preNode.next = head
#         head.prev = preNode
            
#         slicesN = len(slices)
#         fullMask = (1 << slicesN -1)
            
#         dp = {}
        
#         def takePizza(m0, leftOver):
            
#             if m0 in dp:
#                 return dp[m0]
#             subAns = 0
#             if leftOver == 3:
#                 subAns = 0
#                 pointer = head.next
#                 while pointer != head:
#                     subAns = max(subAns, pointer.val)
#                     # print(pointer.val, pointerDict[pointer])
#                     pointer = pointer.next 
#                 # print(subAns)
#                 dp[m0] = subAns
#                 return subAns            
#             pointer = head.next
#             while pointer != head:
#                 m1 = m0|(1<<pointerDict[pointer])
#                 if pointer.next == head:
#                     endPointer = head.next
#                     m1 |= (1<<pointerDict[head.next])
#                 else:
#                     endPointer = pointer.next
#                     m1 |= (1<<pointerDict[pointer.next])
#                 if pointer.prev == head:
#                     startPointer = head.prev
#                     m1 |= (1<<pointerDict[head.prev])
#                 else:
#                     startPointer = pointer.prev
#                     m1 |= (1<<pointerDict[pointer.prev])    
                
                
#                 if pointer.next == head or pointer.prev == head:  
#                     headPrev = head.prev
#                     headNext = head.next
#                     head.next = endPointer.next
#                     head.prev = startPointer.prev
#                     head.prev.next = head
#                     head.next.prev = head
#                     subAns = max(subAns, pointer.val + takePizza(m1, leftOver-3))
#                     head.prev = headPrev
#                     head.next = headNext
#                 else:
#                     startPointer.prev.next = endPointer.next
#                     endPointer.next.prev = startPointer.prev
#                     subAns = max(subAns, pointer.val + takePizza(m1, leftOver-3))
#                 startPointer.prev.next = startPointer
#                 startPointer.next.pre = startPointer                    
#                 pointer.prev.next = pointer
#                 pointer.next.prev = pointer
#                 endPointer.prev.next = endPointer
#                 endPointer.next.pre = endPointer 
                
#                 pointer = pointer.next
#             dp[m0] = subAns
#             return subAns
#         return takePizza(0, slicesN)
            
            
            
            
            


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        nPick = n//3
        total = [[[0] * (n + 1) for _ in range(nPick+1)] for __ in range(2)]
        total[1][1][1] = slices[0]
        
        
        for i in range(1, nPick+1):
            for j in range(2, n + 1):
                total[0][i][j] = max(slices[j-1] + total[0][i-1][j-2], total[0][i][j-1])
                total[1][i][j] = max(slices[j-1] + total[1][i-1][j-2], total[1][i][j-1])
        
        return max(max(total[0][nPick]), max(total[1][nPick][:-1]))
            
        


class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n_picks = len(w)//3
        
        dp1 = [[0 for _ in range(len(w))] for _ in range(n_picks+1)]
        dp2 = [[0 for _ in range(len(w))] for _ in range(n_picks+1)]
        
        for i in range(1,n_picks+1):
            for j in range(1,len(w)):
                
                if j == 1:
                    dp1[i][j] = w[j-1]
                    dp2[i][j] = w[j]
                    continue
                dp1[i][j] = max(w[j-1] + dp1[i-1][j-2],dp1[i][j-1])
                dp2[i][j] = max(w[j] + dp2[i-1][j-2],dp2[i][j-1])
        
        return max(dp1[n_picks][len(w)-1],dp2[n_picks][len(w)-1])

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        
        def find(arr,n):
            dp1=[0 for i in range(n+1)]
            dp2=[0 for i in range(n+1)]
            dp2[1]=arr[0]
            for i in range(1,len(arr)):
                new_dp1=[max(dp1[j],dp2[j]) for j in range(n+1)]
                new_dp2=[0]+[arr[i]+dp1[j-1] for j in range(1,n+1)]
                dp1=new_dp1
                dp2=new_dp2
            return max(dp2[-1],dp1[-1])
        n=len(slices)//3
        return max(find(slices[:-1],n),find(slices[1:],n))
                


class Solution:
    def maxSizeSlices(self, s: List[int]) -> int:
        ct = len(s)//3
        @lru_cache(None)
        def f(l, r, n):
            if n == 0:
                return 0
            if l > r:
                return -1e18
            if n == 1:
                return max(s[l:r+1])
            return max(f(l+1, r, n), s[l] + f(l+2, r, n-1))
        return max(f(1, len(s)-1, ct), s[0] + f(2, len(s)-2, ct-1))

class Solution:
  def dp(self, i, j, k, l):
    # max by taking k from s[i:j] assume cycle if l = 1 else no-cycle
    if (i, j, k, l) not in self.memo:
      if k == 1:
        self.memo[(i, j, k, l)] = max(self.s[i:j])
      elif j - i < 2 * k - 1:
        self.memo[(i, j, k, l)] = float('-inf')
      else:
        # max of taking self.s[i] and not taking self.s[i] at this step
        self.memo[(i, j, k, l)] = max(self.dp(i + 2, j - l, k - 1, 0) + self.s[i], self.dp(i + 1, j, k, 0))
    return self.memo[(i, j, k, l)]
  def maxSizeSlices(self, slices: List[int]) -> int:
    # Q0213, dynamic programming
    self.memo, self.s, n = {}, slices, len(slices)
    return self.dp(0, n, n // 3, 1)

from functools import lru_cache

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3
        dp1 = [[0] * n for _ in range(k + 1)]

        results = [0, 0]
        for offset in range(2):
            for i in range(1, k + 1):
                dp1[i][1] = w[offset]
                for j in range(2, n):
                    dp1[i][j] = max(dp1[i - 1][j - 2] + w[j - 1 + offset], dp1[i][j - 1])
            results[offset] = dp1[-1][-1]

        return max(results)


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        l=len(slices)
        s1=slices[0:l-1]
        s2=slices[1:l]
        n=l//3
        
        def summax(arr):
        
            dp=[[0]*(n+1) for i in range(l+1)]
            p=len(arr)
            for i in range(1,p+1):
                for j in range(1,n+1):
                    if j>i:
                        break
        
                    if i==1:
                        dp[i][j]=arr[0]
                    else:
                        dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+arr[i-1])
                        
            return dp[p][n]
        
        return max(summax(s1),summax(s2))


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        original = slices
        slices = slices[:-1]
        dp = [[0 for j in range(len(original) // 3 + 1)] for i in range(len(slices) + 1)]
        
        for j in range(1, len(original) // 3 + 1):
            dp[1][j] = slices[0]
        
        for j in range(1, len(dp[0])):
            for i in range(2, len(dp)):
                dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i - 1], dp[i][j])
        ans = dp[-1][-1]
        slices = original[1:]

        dp = [[0 for j in range(len(original) // 3 + 1)] for i in range(len(slices) + 1)]
        
        for j in range(1, len(original) // 3 + 1):
            dp[1][j] = slices[0]
        
        for j in range(1, len(dp[0])):
            for i in range(2, len(dp)):
                dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i - 1], dp[i][j])
        

        ans = max(ans, dp[-1][-1])
        return ans
            


class Solution(object):
    def maxSizeSlices(self, A):
        N = len(A)
        A.extend(A)
        NINF = float('-inf')

        @lru_cache(None)
        def dp(i, j, rem):
            if rem == 0:
                return 0
            elif i > j:
                return NINF
            else:
                return max(dp(i+2, j, rem-1) + A[i], dp(i+1, j, rem))

        return max(A[0] + dp(2, N - 2, N // 3 - 1), dp(1, N - 1, N // 3))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        @lru_cache(None)
        def dp(i, remaining, version):
            if i > len(slices) - version:
                return 0
            if remaining == 0:
                return 0
            else:
                return max(dp(i + 1, remaining, version), slices[i] + dp(i + 2, remaining - 1, version))
        return max(dp(1, len(slices) // 3, 1), dp(0, len(slices) // 3, 2))

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        k = len(w)//3
        
        dp1 = [[0]*(len(w)) for _ in range(k+1)]
        dp2 = [[0]*(len(w)) for _ in range(k+1)]
        
        for n in range(1,k+1):
            for i in range(1,len(w)):
                
                if i==1:
                    dp1[n][i] = w[i-1]
                    dp2[n][i] = w[i]
                    continue
                
                dp1[n][i] = max(dp1[n-1][i-2]+w[i-1],dp1[n][i-1])
                dp2[n][i] = max(dp2[n-1][i-2]+w[i],dp2[n][i-1])
        return max(dp1[-1][-1],dp2[-1][-1])

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        N = len(slices)
        
        @lru_cache(None)
        def dp(i, k, d):
            if 3*k == N:
                return 0
            if i >= N-d:
                return -math.inf
            return max(slices[i] + dp(i+2, k+1, d), dp(i+1, k, d))
        
        return max(slices[0] + dp(2, 1, 1), dp(1, 0, 0))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        # find a subseq in circle without disjoint element....
        n = len(slices) // 3
        
        def get_maxsubseq(pieces):
            #dp(i, j) = max(dp(i-1, j-2) + pieces[j], dp(i, j-1))
            m = len(pieces)
            dp = {}
            for i in range(1, n+1):
                tdp = {}
                for j in range(m):
                    tdp[j] = max(dp.get(j-2, 0) + pieces[j], tdp.get(j-1, 0))
                    
                dp = tdp
            return dp[m-1]
        
        return max(get_maxsubseq(slices[1:]), get_maxsubseq(slices[:-1]))
                
            


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        m = len(slices)
        slices1 = slices[0:m-1]
        slices2 = slices[1:]
        n = m // 3
        def helper(arr, n):
            m = len(arr)
            
            # dp[i][j] represents max sum when pick j elements from array of length i
            dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
            for i in range(1,m + 1):
                for j in range(1, n + 1):
                    if i == 1:
                        dp[i][j] = arr[0]
                    else:
                        dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + arr[i - 1])
                        
            return dp[m][n]
                        
        return max(helper(slices1, n), helper(slices2, n))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        # select 1 -> max of selecting n-1 from 2, 3n-1
        # not select 1 -> max of selecting n from 2, 3n                                                                 
        # a table to fill: (either selected or not)
        #  1, 2, 3, ... 3n # pos
        #0  maxSum
        #1
        #2
        #
        #n
        #num selected
        N = len(slices) // 3
        dpOn = [[-1 for i in range(3 * N)] for j in range(N+1)]
        dpOff = [[-1 for i in range(3 * N)] for j in range(N+1)]
        
        # first 1 selected
        dpOn[1][0] = slices[0]
        
        for i in range(1, 3*N):
            dpOff[0][i] = 0
            
        for i in range(1, 3*N):
            for j in range(1, N+1):
                dpOff[j][i] = max(dpOn[j][i-1], dpOff[j][i-1])
                if dpOff[j-1][i-1] == -1:
                    dpOn[j][i] = -1
                else:
                    dpOn[j][i] = dpOff[j-1][i-1] + slices[i]
        
        maxVal = dpOff[N][3*N-1]
        
        dpOn = [[-1 for i in range(3 * N)] for j in range(N+1)]
        dpOff = [[-1 for i in range(3 * N)] for j in range(N+1)]
        # first 1 not selected
        for i in range(0, 3*N):
            dpOff[0][i] = 0

        for i in range(1, 3*N):
            for j in range(1, N+1):
                dpOff[j][i] = max(dpOn[j][i-1], dpOff[j][i-1])
                if dpOff[j-1][i-1] == -1:
                    dpOn[j][i] = -1
                else:
                    dpOn[j][i] = dpOff[j-1][i-1] + slices[i]
        
        maxVal = max(maxVal, dpOn[N][3*N-1], dpOff[N][3*N-1])
        
        return maxVal

from functools import *
class Solution(object):
    def maxSizeSlices(self, slices):
        @lru_cache(None)
        def dp(start, end, k):
            if k ==0:
                return 0
            if k ==  1:
                return max(slices[start:end+1])
            if end-start+1<k*2-1:
                return -float('inf')
            return max(dp(start+2, end, k-1)+slices[start], dp(start+1, end, k))
        n = len(slices)//3
        return max(dp(0, len(slices)-2, n), dp(1, len(slices)-1, n))


from typing import List, Dict, Set, Optional
from enum import Enum
from functools import lru_cache


class Person(Enum):
    ME = 0
    ALICE = 1
    BOB = 2


class DoublyLinkedListNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.prev = None
        self.next = None


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        @lru_cache(None)
        def dfs(pizza_slice: int, max_slice: int, level: int) -> int:
            if level == len(slices) / 3:
                return 0

            if pizza_slice > max_slice:
                return 0

            return max(
                dfs(pizza_slice + 2, max_slice, level + 1) + slices[pizza_slice],
                dfs(pizza_slice + 1, max_slice, level),
            )

        return max(dfs(1, len(slices) - 1, 0), dfs(0, len(slices) - 2, 0))




    def maxSizeSlicesBruteForce(self, slices: List[int]) -> int:
        slices_nodes = [DoublyLinkedListNode(pos) for pos in range(len(slices))]

        for pizza_slice_pos in range(len(slices)):
            prev_pizza_slice_pos = (pizza_slice_pos - 1) % len(slices)
            next_pizza_slice_pos = (pizza_slice_pos + 1) % len(slices)

            pizza_slice = slices_nodes[pizza_slice_pos]
            prev_pizza_slice = slices_nodes[prev_pizza_slice_pos]
            next_pizza_slice = slices_nodes[next_pizza_slice_pos]

            prev_pizza_slice.next = pizza_slice
            pizza_slice.prev = prev_pizza_slice

            pizza_slice.next = next_pizza_slice
            next_pizza_slice.prev = pizza_slice

        def dfs(pizza_slices_left: Set[int]) -> int:
            result = 0
            for pizza_slice_pos in list(pizza_slices_left):
                pizza_slice = slices_nodes[pizza_slice_pos]

                prev_pizza_slice = pizza_slice.prev
                next_pizza_slice = pizza_slice.__next__

                prev_prev_pizza_slice = prev_pizza_slice.prev
                next_next_pizza_slice = next_pizza_slice.__next__

                prev_prev_pizza_slice.next = next_next_pizza_slice
                next_next_pizza_slice.prev = prev_prev_pizza_slice

                pizza_slices_left.remove(pizza_slice.val)
                pizza_slices_left.remove(prev_pizza_slice.val)
                pizza_slices_left.remove(next_pizza_slice.val)

                result = max(result, dfs(pizza_slices_left) + slices[pizza_slice.val])

                pizza_slices_left.add(pizza_slice.val)
                pizza_slices_left.add(prev_pizza_slice.val)
                pizza_slices_left.add(next_pizza_slice.val)

                prev_prev_pizza_slice.next = prev_pizza_slice
                next_next_pizza_slice.prev = next_pizza_slice

            return result

        return dfs(set(range(len(slices))))


class TestSolution:
    def setup(self) -> None:
        self.sol = Solution()

    def test_case1(self) -> None:
        assert self.sol.maxSizeSlices([1,2,3,4,5,6]) == 10

    def test_case2(self) -> None:
        assert self.sol.maxSizeSlices([6,3,1,2,6,2,4,3,10,4,1,4,6,5,5,3,4,7,6,5,8,7,3,8,8,1,7,1,7,8]) == 10


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        N = len(slices)
        target = N//3
        dp = [[-1 for x in range(target)] for y in range(N)]
        
        def dfs(idx: int, cnt: int) -> int:
            if cnt >= target or idx >= N:
                return 0
            
            if dp[idx][cnt] == -1:
                dp[idx][cnt] = max(dfs(idx+1, cnt), slices[idx]+dfs(idx+2, cnt+1))
            return dp[idx][cnt]
            
        result = dfs(1, 0)
        dp = [[-1 for x in range(target)] for y in range(N)]
        N -= 1
        result = max(result, dfs(0, 0))
        
        return result

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n=len(slices)
        dp=[[0 for j in range(n//3)] for i in range(n)]
        
        dp[0][0]=slices[0]
        
        for i in range(1,n):
            dp[i][0]=max(dp[i-1][0],slices[i])
        
        for i in range(2,n):
            for j in range(1,min(i//2+1,n//3)):
                dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+slices[i])
        
        mx=0
        
        for i in range(n-1):
            mx=max(mx,dp[i][-1])
            
        for i in range(n):
            for j in range(n//3):
                dp[i][j]=0
        
        for i in range(1,n):
            dp[i][0]=max(dp[i-1][0],slices[i])
        
        for i in range(2,n):
            for j in range(1,min(i//2+1,n//3)):
                dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+slices[i])
        
        mx=max(mx,dp[-1][-1])
        return mx

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n_picks = len(w)//3
        
        dp1 = [[0 for _ in range(len(w))] for _ in range(n_picks+1)]
        dp2 = [[0 for _ in range(len(w))] for _ in range(n_picks+1)]
        
        for i in range(1,n_picks+1):
            for j in range(1,len(w)):
                
                if j == 1:
                    dp1[i][j] = w[j-1]
                    dp2[i][j] = w[j]
                    continue
                dp1[i][j] = max(w[j-1] + dp1[i-1][j-2],dp1[i][j-1])
                dp2[i][j] = max(w[j] + dp2[i-1][j-2],dp2[i][j-1])
        
        return max(dp1[n_picks][len(w)-1],dp2[n_picks][len(w)-1])
    


from functools import lru_cache

class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3
        dp1 = [[0] * n for _ in range(k + 1)]
        dp2 = [[0] * n for _ in range(k + 1)]
        for i in range(1, k + 1):
            dp1[i][1] = w[0]
            dp2[i][1] = w[1]
            for j in range(2, len(w)):
                dp1[i][j] = max(dp1[i - 1][j - 2] + w[j - 1], dp1[i][j - 1])
                dp2[i][j] = max(dp2[i - 1][j - 2] + w[j], dp2[i][j - 1])
        return max(dp1[-1][-1], dp2[-1][-1])

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        memo = {}
        def solve(i, j, k):
            if k == 0:
                return 0
            elif i > j:
                return 0
            elif (i, j, k) in memo:
                return memo[(i, j, k)]
            memo[(i, j, k)] = max(slices[i]+solve(i+2, j, k-1), solve(i+1, j, k))
            return memo[(i, j, k)]
        return max(solve(0, n-2, n//3), solve(1, n-1, n//3))

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        N = len(slices)
        
        @lru_cache(None)
        def rec(cur, taken, avoid_last):
            if taken * 3 > N:
                return -math.inf
            if cur >= N:
                return 0 if taken * 3 == N else -math.inf
            
            ans = rec(cur+1, taken, avoid_last)
            if avoid_last and cur == N-1:
                return ans
            ans = max(ans, rec(cur+2, taken+1, avoid_last | (cur == 0)) + slices[cur])
            
            return ans
        
        return rec(0, 0, False)

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        @lru_cache(None)
        def dp(i, j, k):
            if k == 0:
                return 0
            elif i >= j:
                return -math.inf
            else:
                return max(
                    slices[i] + dp(i + 2, j, k - 1),
                    dp(i + 1, j, k)
                )

        n = len(slices)
        s = n // 3
        return max(
            dp(1, n, s),
            dp(0, n - 1, s)
        )

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices) // 3
        if n == 1:
            return max(slices)
        
        @lru_cache(None)
        def process(f, p, i, k):
            if i == 0:
                return slices[0] if f == 1 else 0
            
            if p == 1:
                return process(f, 0, i-1, k)
            else:
                if (i == 1 and f == 1) or k == 0:
                    return process(f, 0, i-1, k)
                else:
                    return max(process(f, 0, i-1, k), slices[i]+process(f, 1, i-1, k-1))
        
        return max(process(0, 0, 3*n-1, n), process(1, 1, 3*n-1, n-1))

                    
            
            
            
            
            
        


from typing import List, Dict, Set, Optional
from enum import Enum
from functools import lru_cache


class Person(Enum):
    ME = 0
    ALICE = 1
    BOB = 2


class DoublyLinkedListNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.prev = None
        self.next = None


class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        levels = len(slices) // 3 + 1
        result = 0
        for start, stop in ((0, len(slices) - 1), (1, len(slices))):
            dp = [[0] * levels for _ in range(len(slices) + 2)]

            for pizza_slice in reversed(list(range(start, stop))):
                for level in range(levels):
                    if pizza_slice + 2 < len(dp) and level < levels - 1:
                        dp[pizza_slice][level] = max(
                            dp[pizza_slice][level],
                            dp[pizza_slice + 2][level + 1] + slices[pizza_slice],
                        )

                    dp[pizza_slice][level] = max(
                        dp[pizza_slice][level],
                        dp[pizza_slice + 1][level],
                    )

            result = max(result, dp[start][0])

        return result


    def maxSizeSlicesTopDown(self, slices: List[int]) -> int:
        @lru_cache(None)
        def dfs(pizza_slice: int, max_slice: int, level: int) -> int:
            if level == len(slices) / 3:
                return 0

            if pizza_slice > max_slice:
                return 0

            return max(
                dfs(pizza_slice + 2, max_slice, level + 1) + slices[pizza_slice],
                dfs(pizza_slice + 1, max_slice, level),
            )

        return max(dfs(1, len(slices) - 1, 0), dfs(0, len(slices) - 2, 0))

    def maxSizeSlicesBruteForce(self, slices: List[int]) -> int:
        slices_nodes = [DoublyLinkedListNode(pos) for pos in range(len(slices))]

        for pizza_slice_pos in range(len(slices)):
            prev_pizza_slice_pos = (pizza_slice_pos - 1) % len(slices)
            next_pizza_slice_pos = (pizza_slice_pos + 1) % len(slices)

            pizza_slice = slices_nodes[pizza_slice_pos]
            prev_pizza_slice = slices_nodes[prev_pizza_slice_pos]
            next_pizza_slice = slices_nodes[next_pizza_slice_pos]

            prev_pizza_slice.next = pizza_slice
            pizza_slice.prev = prev_pizza_slice

            pizza_slice.next = next_pizza_slice
            next_pizza_slice.prev = pizza_slice

        def dfs(pizza_slices_left: Set[int]) -> int:
            result = 0
            for pizza_slice_pos in list(pizza_slices_left):
                pizza_slice = slices_nodes[pizza_slice_pos]

                prev_pizza_slice = pizza_slice.prev
                next_pizza_slice = pizza_slice.__next__

                prev_prev_pizza_slice = prev_pizza_slice.prev
                next_next_pizza_slice = next_pizza_slice.__next__

                prev_prev_pizza_slice.next = next_next_pizza_slice
                next_next_pizza_slice.prev = prev_prev_pizza_slice

                pizza_slices_left.remove(pizza_slice.val)
                pizza_slices_left.remove(prev_pizza_slice.val)
                pizza_slices_left.remove(next_pizza_slice.val)

                result = max(result, dfs(pizza_slices_left) + slices[pizza_slice.val])

                pizza_slices_left.add(pizza_slice.val)
                pizza_slices_left.add(prev_pizza_slice.val)
                pizza_slices_left.add(next_pizza_slice.val)

                prev_prev_pizza_slice.next = prev_pizza_slice
                next_next_pizza_slice.prev = next_pizza_slice

            return result

        return dfs(set(range(len(slices))))


class TestSolution:
    def setup(self) -> None:
        self.sol = Solution()

    def test_case1(self) -> None:
        assert self.sol.maxSizeSlices([1,2,3,4,5,6]) == 10

    def test_case2(self) -> None:
        assert self.sol.maxSizeSlices([6,3,1,2,6,2,4,3,10,4,1,4,6,5,5,3,4,7,6,5,8,7,3,8,8,1,7,1,7,8]) == 10


class Solution:
    def maxSizeSlices(self, w: List[int]) -> int:
        n = len(w)
        k = n // 3

        results = [0, 0]
        for offset in range(2):
            cur = [0] * n
            prev = [0] * n
            for _ in range(k):
                cur[1] = w[offset]
                for j in range(2, n):
                    cur[j] = max(prev[j - 2] + w[j - 1 + offset], cur[j - 1])
                prev[:] = cur
                cur[:] = [0] * n
            results[offset] = prev[-1]

        return max(results)