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: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

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):
			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):
					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
			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):
			a = [0] * (n + 1)
			b = [0] * (n + 1)
			for x in arr:
				(a, b) = (b, [i and max(x + a[i - 1], b[i]) for i in range(n + 1)])
			return b[-1]
		return max(linear(slices[1:]), linear(slices[:-1]))


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)
			return dp[n][-1]
		return max(max_adj_sum(slices[1:]), max_adj_sum(slices[:-1]))


class Solution:

	def maxSizeSlices(self, slices: List[int]) -> int:
		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])
		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
		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)
		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]


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


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, 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 -1e+18
			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):
		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:
				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:
		(self.memo, self.s, n) = ({}, slices, len(slices))
		return self.dp(0, n, n // 3, 1)


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, 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:
		n = len(slices) // 3

		def get_maxsubseq(pieces):
			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 = [[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:
		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)]
		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)]
		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, 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)
			elif 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))


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)