You are given an array A of size N. The array contains integers and is of even length. The elements of the array represent N coin of values V_{1}, V_{2}, ....V_{n}. You play against an opponent in an alternating way. 
In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin.
You need to determine the maximum possible amount of money you can win if you go first.
Note: Both the players are playing optimally.
Example 1:
Input:
N = 4
A[] = {5,3,7,10}
Output: 15
Explanation: The user collects maximum
value as 15(10 + 5)
Example 2:
Input:
N = 4
A[] = {8,15,3,7}
Output: 22
Explanation: The user collects maximum
value as 22(7 + 15)
Your Task:
Complete the function maximumAmount() which takes an array arr[] (represent values of N coins) and N as number of coins as a parameter and returns the maximum possible amount of money you can win if you go first.
Expected Time Complexity : O(N*N)
Expected Auxiliary Space: O(N*N)
Constraints:
2 <= N <= 10^{3}
1 <= A_{i} <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3


#Function to find the maximum possible amount of money we can win.
class Solution:
    def optimalStrategyOfGame(self,arr, n):
        # code here

Solutions:
class Solution:

	def rec_sol(self, arr, start, end, memo):
		if (start, end) in memo:
			return memo[start, end]
		if start + 1 == end:
			return max(arr[start], arr[end])
		memo[start, end] = max(arr[start] + min(self.rec_sol(arr, start + 2, end, memo), self.rec_sol(arr, start + 1, end - 1, memo)), arr[end] + min(self.rec_sol(arr, start + 1, end - 1, memo), self.rec_sol(arr, start, end - 2, memo)))
		return memo[start, end]

	def optimalStrategyOfGame(self, arr, n):
		dp = {}
		return self.rec_sol(arr, 0, n - 1, dp)


class Solution:

	def solve(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		strt = arr[i] + min(self.solve(arr, i + 2, j, dp), self.solve(arr, i + 1, j - 1, dp))
		last = arr[j] + min(self.solve(arr, i + 1, j - 1, dp), self.solve(arr, i, j - 2, dp))
		dp[i][j] = max(strt, last)
		return dp[i][j]

	def optimalStrategyOfGame(self, arr, n):
		j = n - 1
		i = 0
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.solve(arr, i, j, dp)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for i in range(n)] for j in range(n)]
		return self.func(arr, n, 0, n - 1, dp)

	def func(self, arr, n, i, j, dp):
		if i >= j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		num1 = arr[i] + min(self.func(arr, n, i + 2, j, dp), self.func(arr, n, i + 1, j - 1, dp))
		num2 = arr[j] + min(self.func(arr, n, i + 1, j - 1, dp), self.func(arr, n, i, j - 2, dp))
		dp[i][j] = max(num1, num2)
		return dp[i][j]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for gap in range(n):
			for i in range(n - gap):
				j = i + gap
				if i == j:
					dp[i][j] = arr[i]
				elif i + 1 == j:
					dp[i][j] = max(arr[i], arr[j])
				else:
					val1 = arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1])
					val2 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					dp[i][j] = max(val1, val2)
		return dp[0][-1]


def fun(nums, i, j, memo):
	if (i, j) in memo:
		return memo[i, j]
	if i == j:
		return nums[i]
	if i + 1 == j:
		return max(nums[i], nums[j])
	memo[i, j] = max(nums[i] + min(fun(nums, i + 2, j, memo), fun(nums, i + 1, j - 1, memo)), nums[j] + min(fun(nums, i + 1, j - 1, memo), fun(nums, i, j - 2, memo)))
	return memo[i, j]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		return fun(arr, 0, len(arr) - 1, {})


def coins_game(coins):
	n = len(coins)
	memo = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		memo[i][i] = coins[i]
	for i in range(n - 1):
		memo[i][i + 1] = max(coins[i], coins[i + 1])
	for i in range(n - 2, -1, -1):
		for j in range(i + 2, n):
			memo[i][j] = max(coins[i] + min(memo[i + 2][j], memo[i + 1][j - 1]), coins[j] + min(memo[i + 1][j - 1], memo[i][j - 2]))
	return memo[0][n - 1]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		return coins_game(arr)


def optimalStrategyOfGame(arr, n):
	table = [[0 for i in range(n)] for i in range(n)]
	for gap in range(n):
		for j in range(gap, n):
			i = j - gap
			x = 0
			if i + 2 <= j:
				x = table[i + 2][j]
			y = 0
			if i + 1 <= j - 1:
				y = table[i + 1][j - 1]
			z = 0
			if i <= j - 2:
				z = table[i][j - 2]
			table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
	return table[0][n - 1]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		return optimalStrategyOfGame(arr, n)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		cache = [[0 for _ in range(n)] for i in range(n)]

		def dfs(start, end):
			if end < start:
				return 0
			elif not cache[start][end]:
				cache[start][end] = max(arr[start] + min(dfs(start + 2, end), dfs(start + 1, end - 1)), arr[end] + min(dfs(start + 1, end - 1), dfs(start, end - 2)))
			return cache[start][end]
		return dfs(0, n - 1)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for j in range(n + 1)] for i in range(n + 1)]

		def foo(dp, i, j):
			if i > j:
				return 0
			if dp[i][j] == -1:
				res = max(arr[i] + min(foo(dp, i + 2, j), foo(dp, i + 1, j - 1)), arr[j] + min(foo(dp, i + 1, j - 1), foo(dp, i, j - 2)))
				dp[i][j] = res
			return dp[i][j]
		return foo(dp, 0, n - 1)


class Solution:

	def solve(self, arr, i, j, dp):
		if i >= n or j < 0 or i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		use_i = arr[i] + min(self.solve(arr, i + 2, j, dp), self.solve(arr, i + 1, j - 1, dp))
		use_j = arr[j] + min(self.solve(arr, i, j - 2, dp), self.solve(arr, i + 1, j - 1, dp))
		dp[i][j] = max(use_i, use_j)
		return dp[i][j]

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for a in range(n + 1)] for b in range(n + 1)]
		a = self.solve(arr, 0, n - 1, dp)
		return a


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				x = 0
				y = 0
				z = 0
				if i + 2 < j:
					x = dp[i + 2][j]
					y = dp[i + 1][j - 1]
					z = dp[i][j - 2]
				dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
		return dp[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1] * n for i in range(n)]

		def findoptimalsol(l, r, n):
			if l > r:
				return 0
			if dp[l][r] != -1:
				return dp[l][r]
			val = 0
			left = arr[l] + min(findoptimalsol(l + 2, r, n), findoptimalsol(l + 1, r - 1, n))
			right = arr[r] + min(findoptimalsol(l + 1, r - 1, n), findoptimalsol(l, r - 2, n))
			val = max(left, right)
			dp[l][r] = val
			return val
		return findoptimalsol(0, n - 1, n)


def solve(a, i, j, dp):
	if dp[i][j] != -1:
		return dp[i][j]
	if i == j:
		dp[i][j] = a[i]
		return dp[i][j]
	if i == j - 1:
		dp[i][j] = max(a[i], a[j])
		return dp[i][j]
	aa = a[i] + min(solve(a, i + 2, j, dp), solve(a, i + 1, j - 1, dp))
	b = a[j] + min(solve(a, i + 1, j - 1, dp), solve(a, i, j - 2, dp))
	dp[i][j] = max(aa, b)
	return dp[i][j]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return solve(arr, 0, n - 1, dp)


class Solution:

	def optimalStrategyOfGame(self, arr, n):

		def funk(i, j):
			return j * n + i
		dp = [0] * (n * n)
		for i in range(n):
			dp[funk(i, i)] = arr[i]
		for r in range(1, n):
			for j in range(0, n - r):
				s = j
				e = j + r
				dp[funk(s, e)] = max(arr[s] - dp[funk(s + 1, e)], arr[e] - dp[funk(s, e - 1)])
		return (dp[funk(0, n - 1)] + sum(arr)) // 2


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1] * n for _ in range(n)]

		def find(start, end):
			n = end - start
			if n == 2:
				return max(arr[start:end])
			if n == 1:
				return arr[start]
			if dp[start][end - 1] != -1:
				return dp[start][end - 1]
			a = arr[start] + min(find(start + 2, end), find(start + 1, end - 1))
			b = arr[end - 1] + min(find(start, end - 2), find(start + 1, end - 1))
			dp[start][end - 1] = max(a, b)
			return dp[start][end - 1]
		return find(0, n)


class Solution:

	def optimalStrategyOfGame(self, arr, n):

		def game(i, j, arr, dp):
			if i > j or i >= n or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			take1 = arr[i] + min(game(i + 1, j - 1, arr, dp), game(i + 2, j, arr, dp))
			take2 = arr[j] + min(game(i, j - 2, arr, dp), game(i + 1, j - 1, arr, dp))
			dp[i][j] = max(take1, take2)
			return max(take1, take2)
		dp = [[-1] * n for x in range(n)]
		return game(0, n - 1, arr, dp)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		total_sum = [0] * n
		total_sum[0] = arr[0]
		for i in range(1, n):
			total_sum[i] = total_sum[i - 1] + arr[i]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				tot_sum = total_sum[j] - total_sum[i - 1] if i > 0 else total_sum[j]
				if j == i:
					dp[i][j] = arr[i]
				else:
					dp[i][j] = tot_sum - min(dp[i + 1][j], dp[i][j - 1])
		return dp[0][n - 1]


from functools import lru_cache

class Solution:

	def optimalStrategyOfGame(self, a, n):
		dp = {}

		def fun(i, j):
			if i > j:
				return 0
			if i == j:
				return a[i]
			if (i, j) in dp:
				return dp[i, j]
			opt1 = a[i] + min(fun(i + 2, j), fun(i + 1, j - 1))
			opt2 = a[j] + min(fun(i, j - 2), fun(i + 1, j - 1))
			dp[i, j] = max(opt1, opt2)
			return dp[i, j]
		ans = fun(0, n - 1)
		return ans


import sys
sys.setrecursionlimit(5000)

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		hmap = {}

		def optimal(arr, i, j):
			if i == j:
				return arr[i]
			if i > j:
				return 0
			if (i, j) not in hmap:
				choice1 = arr[i] + min(optimal(arr, i + 1, j - 1), optimal(arr, i + 2, j))
				choice2 = arr[j] + min(optimal(arr, i, j - 2), optimal(arr, i + 1, j - 1))
				hmap[i, j] = max(choice1, choice2)
			return hmap[i, j]
		return optimal(arr, 0, n - 1)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1] * (n + 1) for _ in range(n + 1)]

		def solve(i, j):
			if i >= j:
				return 0
			if i >= n or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			a = arr[i] + solve(i + 2, j)
			b = arr[i] + solve(i + 1, j - 1)
			c = arr[j] + solve(i + 1, j - 1)
			d = arr[j] + solve(i, j - 2)
			t = max(min(a, b), min(c, d))
			dp[i][j] = t
			return t
		ans1 = solve(0, n - 1)
		return ans1


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		a = [[0 for j in range(0, n)] for i in range(0, n)]
		for i in range(0, n):
			a[i][i] = arr[i]
		s = [0] * n
		p = 0
		for i in range(0, n):
			p += arr[i]
			s[i] = p
		for l in range(2, n + 1):
			for i in range(0, n - l + 1):
				if i != 0:
					a[i][i + l - 1] = max(arr[i] + s[i + l - 1] - s[i] - a[i + 1][i + l - 1], arr[i + l - 1] + s[i + l - 2] - s[i - 1] - a[i][i + l - 2])
				else:
					a[i][i + l - 1] = max(arr[i] + s[i + l - 1] - s[i] - a[i + 1][i + l - 1], arr[i + l - 1] + s[i + l - 2] - a[i][i + l - 2])
		return a[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, a, n):

		def recursion(i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			if i >= j:
				return 0
			choice1 = a[i] + min(recursion(i + 2, j), recursion(i + 1, j - 1))
			choice2 = a[j] + min(recursion(i, j - 2), recursion(i + 1, j - 1))
			dp[i][j] = max(choice1, choice2)
			return dp[i][j]
		dp = [[-1 for i in range(n + 1)] for i in range(n + 1)]
		return recursion(0, n - 1)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n - 1):
			dp[i][i + 1] = max(arr[i], arr[i + 1])
		for gap in range(3, n, 2):
			i = 0
			while i + gap < n:
				j = i + gap
				dp[i][j] = max(arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
				i = i + 1
		return dp[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, N):
		dp = [[0 for i in range(N + 1)] for j in range(3)]
		for i in range(N - 1, -1, -1):
			dp[0][i] = arr[i]
			for j in range(i + 1, N):
				take_left = arr[i] + min(dp[2][j], dp[1][j - 1])
				take_right = arr[j] + min(dp[0][j - 2], dp[1][j - 1])
				dp[0][j] = max(take_left, take_right)
			(dp[1], dp[2]) = (dp[2], dp[1])
			(dp[0], dp[1]) = (dp[1], dp[0])
		return dp[1][-2]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		A = [[max(arr[i], arr[j]) if j - i == 1 else arr[i] if i == j else 0 for j in range(n)] for i in range(n)]
		for j in range(2, n):
			for i in range(j - 2, -1, -1):
				A[i][j] = max(arr[i] + min(A[i + 2][j], A[i + 1][j - 1]), arr[j] + min(A[i][j - 2], A[i + 1][j - 1]))
		return A[0][n - 1]


class Solution:

	def __maximum_amt_helper(self, i, j, arr):
		if i > j:
			return 0
		if i == j:
			return arr[i]
		if self.dp[i][j] == None:
			take_left = arr[i] + min(self.__maximum_amt_helper(i + 2, j, arr), self.__maximum_amt_helper(i + 1, j - 1, arr))
			take_right = arr[j] + min(self.__maximum_amt_helper(i, j - 2, arr), self.__maximum_amt_helper(i + 1, j - 1, arr))
			self.dp[i][j] = max(take_left, take_right)
		return self.dp[i][j]

	def optimalStrategyOfGame(self, arr, N):
		self.dp = [[None for i in range(N)] for j in range(N)]
		return self.__maximum_amt_helper(0, N - 1, arr)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		front1 = [0] * n
		front2 = [0] * n
		for i in range(n - 1, -1, -1):
			curr = [0] * n
			for j in range(i, n):
				left = arr[i] + min(front2[j], front1[j - 1])
				right = arr[j] + min(front1[j - 1], curr[j - 2])
				curr[j] = max(left, right)
			front2 = front1
			front1 = curr
		return front1[n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0] * n for _ in range(n + 2)]
		for i in range(n):
			dp[i][i] = arr[i]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				left = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
				right = arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
				dp[i][j] = max(left, right)
		return dp[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		prev1 = [V for V in arr]
		prev0 = [max(arr[i], arr[i + 1]) for i in range(len(arr) - 1)]
		for gap in range(2, n):
			newprev0 = []
			for j in range(n - gap):
				newprev0.append(max(arr[j] + min(prev1[j + 1], prev1[j + 2]), arr[j + gap] + min(prev1[j + 1], prev1[j])))
			prev1 = prev0
			prev0 = newprev0
		return prev0[0]


class Solution:

	def optimalStrategyOfGame(self, a, n):
		dp = [[0 for i in range(n)] for i in range(n)]
		for gap in range(n):
			for j in range(gap, n):
				i = j - gap
				x = 0
				y = 0
				z = 0
				if i + 2 <= j:
					x = dp[i + 2][j]
				if i + 1 <= j - 1:
					y = dp[i + 1][j - 1]
				if i <= j - 2:
					z = dp[i][j - 2]
				choice1 = a[i] + min(x, y)
				choice2 = a[j] + min(z, y)
				dp[i][j] = max(choice1, choice2)
		return dp[0][-1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1] * (n + 1) for _ in range(n + 1)]

		def fun(dp, left, right):
			if left > right:
				return 0
			if dp[left][right] != -1:
				return dp[left][right]
			s = arr[left] + min(fun(dp, left + 2, right), fun(dp, left + 1, right - 1))
			l = arr[right] + min(fun(dp, left + 1, right - 1), fun(dp, left, right - 2))
			dp[left][right] = max(l, s)
			return dp[left][right]
		return fun(dp, 0, n - 1)


def solve(arr, i, j, dp):
	if i > j or i >= len(arr) or j < 0:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	op1 = arr[i] + min(solve(arr, i + 2, j, dp), solve(arr, i + 1, j - 1, dp))
	op2 = arr[j] + min(solve(arr, i + 1, j - 1, dp), solve(arr, i, j - 2, dp))
	dp[i][j] = max(op1, op2)
	return dp[i][j]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return solve(arr, 0, n - 1, dp)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def solve(self, arr, n, i, j, flag, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if flag:
			a = arr[i] + self.solve(arr, n, i + 1, j, not flag, dp)
			b = arr[j] + self.solve(arr, n, i, j - 1, not flag, dp)
			dp[i][j] = max(a, b)
			return dp[i][j]
		else:
			a = self.solve(arr, n, i + 1, j, not flag, dp)
			b = self.solve(arr, n, i, j - 1, not flag, dp)
			dp[i][j] = min(a, b)
			return dp[i][j]

	def solution(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		a = arr[i] + min(self.solution(arr, i + 2, j, dp), self.solution(arr, i + 1, j - 1, dp))
		b = arr[j] + min(self.solution(arr, i, j - 2, dp), self.solution(arr, i + 1, j - 1, dp))
		dp[i][j] = max(a, b)
		return dp[i][j]

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for i in range(n + 1)] for j in range(n)]
		return self.solution(arr, 0, n - 1, dp)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		numberOfCoins = n
		coins = arr
		dp = [[0] * numberOfCoins for i in range(numberOfCoins)]
		for i in range(numberOfCoins):
			r = 0
			c = i
			while c < numberOfCoins:
				a = coins[r]
				(a1, a2) = (0, 0)
				if r + 2 <= c:
					a1 = dp[r + 2][c]
				if r + 1 <= c - 1:
					a2 = dp[r + 1][c - 1]
				b = coins[c]
				(b1, b2) = (0, 0)
				if r <= c - 2:
					b1 = dp[r][c - 2]
				if r + 1 <= c - 1:
					b2 = dp[r + 1][c - 1]
				a += min(a1, a2)
				b += min(b1, b2)
				dp[r][c] = max(a, b)
				r += 1
				c += 1
		return dp[0][numberOfCoins - 1]


from sys import setrecursionlimit
setrecursionlimit(10000)

def solver(coins, i, j, dct):
	if i > j:
		return 0
	if i == j:
		return coins[i]
	if (i, j) in dct:
		return dct[i, j]
	a = coins[i] + min(solver(coins, i + 2, j, dct), solver(coins, i + 1, j - 1, dct))
	b = coins[j] + min(solver(coins, i + 1, j - 1, dct), solver(coins, i, j - 2, dct))
	dct[i, j] = max(a, b)
	return max(a, b)

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dct = dict()
		return solver(arr, 0, n - 1, dct)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for i in range(len(arr))] for i in range(n)]
		for i in range(n):
			dp[i][i] = arr[i]
			if i != n - 1:
				dp[i][i + 1] = max(arr[i], arr[i + 1])
		for i in range(2, n):
			(start, end) = (0, i)
			while end < n:
				dp[start][end] = max(arr[end] + min(dp[start][end - 2], dp[start + 1][end - 1]), arr[start] + min(dp[start + 2][end], dp[start + 1][end - 1]))
				start += 1
				end += 1
		return dp[0][-1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		ans = [[0] * n for i in range(n)]
		for d in range(n):
			i = 0
			for j in range(d, n):
				if d == 0:
					ans[i][j] = arr[i]
				elif d == 1:
					ans[i][j] = max(arr[i], arr[j])
				else:
					ans[i][j] = max(arr[j] + min(ans[i][j - 2], ans[i + 1][j - 1]), arr[i] + min(ans[i + 2][j], ans[i + 1][j - 1]))
				i += 1
		return ans[0][-1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		memo = {}

		def recursive(i, j):
			key = (i, j, n)
			if i == j:
				memo[key] = arr[i]
			if i > j:
				memo[key] = 0
			if key in memo:
				return memo[key]
			choice1 = arr[i] + min(recursive(i + 2, j), recursive(i + 1, j - 1))
			choice2 = arr[j] + min(recursive(i + 1, j - 1), recursive(i, j - 2))
			memo[key] = max(choice1, choice2)
			return memo[key]
		return recursive(0, n - 1)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		for diff in range(n):
			for i in range(n - diff):
				j = i + diff
				if i == j:
					dp[i][j] = arr[i]
				elif i + 1 == j:
					dp[i][j] = max(arr[i], arr[j])
				else:
					dp[i][j] = max(arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1]))
		return dp[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		t = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			for j in range(g, n):
				if g == 0:
					t[i][j] = arr[i]
				elif g == 1:
					t[i][j] = max(arr[i], arr[j])
				else:
					val1 = arr[i] + min(t[i + 2][j], t[i + 1][j - 1])
					val2 = arr[j] + min(t[i + 1][j - 1], t[i][j - 2])
					t[i][j] = max(val1, val2)
				i += 1
		return t[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for j in range(n)] for i in range(n)]
		return self.solve(arr, n, 0, n - 1, dp)

	def solve(self, arr, n, i, j, dp):
		if i > j or i >= n or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		picked_i_element = arr[i] + min(self.solve(arr, n, i + 2, j, dp), self.solve(arr, n, i + 1, j - 1, dp))
		picked_j_element = arr[j] + min(self.solve(arr, n, i + 1, j - 1, dp), self.solve(arr, n, i, j - 2, dp))
		dp[i][j] = max(picked_i_element, picked_j_element)
		return dp[i][j]


def solve(arr, i, j, dp):
	if i > j or i >= n or j < 0:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	option1 = arr[i] + min(solve(arr, i + 2, j, dp), solve(arr, i + 1, j - 1, dp))
	option2 = arr[j] + min(solve(arr, i + 1, j - 1, dp), solve(arr, i, j - 2, dp))
	dp[i][j] = max(option1, option2)
	return dp[i][j]

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
		return solve(arr, 0, n - 1, dp)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		N = n
		nums = arr
		dp = [[None for _ in range(N)] for _ in range(N)]
		for i in range(N - 1, -1, -1):
			for j in range(i, N):
				if i == j:
					dp[i][j] = nums[i]
				elif j - i == 1:
					dp[i][j] = max(nums[i], nums[j])
				else:
					dp[i][j] = max(nums[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), nums[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
		return dp[0][N - 1]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		return self.__solve(arr, 0, n - 1, {})

	def __solve(self, arr, start, end, dp):
		if start >= end:
			return 0
		current_key = (start, end)
		if current_key in dp:
			return dp[current_key]
		choose_first = arr[start] + min(self.__solve(arr, start + 2, end, dp), self.__solve(arr, start + 1, end - 1, dp))
		choose_last = arr[end] + min(self.__solve(arr, start + 1, end - 1, dp), self.__solve(arr, start, end - 2, dp))
		result = max(choose_first, choose_last)
		dp[current_key] = result
		return result


class Solution:

	def optimalStrategyOfGame(self, a, n):
		l = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(n - i):
				k = j + i
				if i == 0:
					l[j][k] = a[j]
				elif i == 1:
					l[j][k] = max(a[j], a[k])
				else:
					l[j][k] = max(a[j] + min(l[j + 1][k - 1], l[j + 2][k]), a[k] + min(l[j + 1][k - 1], l[j][k - 2]))
		return l[0][n - 1]


import sys

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		sys.setrecursionlimit(n * 10)
		dp = [[None for j in range(n)] for i in range(n)]

		def f(l, r):
			if l == r:
				return arr[l]
			if dp[l][r]:
				return dp[l][r]
			scorel = arr[l] - f(l + 1, r)
			scorer = arr[r] - f(l, r - 1)
			dp[l][r] = max(scorel, scorer)
			return dp[l][r]
		return (f(0, n - 1) + sum(arr)) // 2


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[None for j in range(n)] for i in range(n)]

		def f(l, r):
			if r == l:
				return arr[l]
			if r == l + 1:
				return max(arr[l], arr[r])
			if dp[l][r]:
				return dp[l][r]
			pointsl = arr[l] + min(f(l + 1, r - 1), f(l + 2, r))
			pointsr = arr[r] + min(f(l + 1, r - 1), f(l, r - 2))
			dp[l][r] = max(pointsl, pointsr)
			return dp[l][r]
		return f(0, n - 1)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1] * n for i in range(n)]

		def findop(s, e):
			if e - s <= 0:
				return 0
			if dp[s][e] != -1:
				return dp[s][e]
			l = arr[s]
			x1 = findop(s + 2, e)
			x2 = findop(s + 1, e - 1)
			l += min(x1, x2)
			r = arr[e]
			y1 = findop(s + 1, e - 1)
			y2 = findop(s, e - 2)
			r += min(y1, y2)
			dp[s][e] = max(l, r)
			return max(l, r)
		return findop(0, n - 1)


import sys
sys.setrecursionlimit(100000)

def oSRec(arr, i, j, Sum, memo):
	if j == i + 1:
		return max(arr[i], arr[j])
	if memo[i][j] != -1:
		return memo[i][j]
	memo[i][j] = max(Sum - oSRec(arr, i + 1, j, Sum - arr[i], memo), Sum - oSRec(arr, i, j - 1, Sum - arr[j], memo))
	return memo[i][j]

def optimalStrategyOfGame1(arr, n):
	MAX = 1010
	memo = [[-1 for i in range(MAX)] for j in range(MAX)]
	Sum = 0
	Sum = sum(arr)
	return oSRec(arr, 0, n - 1, Sum, memo)

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		return optimalStrategyOfGame1(arr, n)


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = [arr[i], 0]
		for i in range(n):
			k = 0
			for j in range(i + 1, n):
				gain_chosing_first_ele = arr[k] + dp[k + 1][j][1]
				gain_choosing_sec_ele = arr[j] + dp[k][j - 1][1]
				if gain_chosing_first_ele > gain_choosing_sec_ele:
					dp[k][j][0] = gain_chosing_first_ele
					dp[k][j][1] = dp[k + 1][j][0]
				else:
					dp[k][j][0] = gain_choosing_sec_ele
					dp[k][j][1] = dp[k][j - 1][0]
				k += 1
		return dp[0][n - 1][0]


class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = (arr[i], 0)
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n):
				a1 = dp[i][j - 1][1] + arr[j]
				a2 = dp[i + 1][j][1] + arr[i]
				if a1 > a2:
					dp[i][j] = (a1, dp[i][j - 1][0])
				else:
					dp[i][j] = (a2, dp[i + 1][j][0])
		return dp[0][n - 1][0]


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def optimalStrategyOfGame(self, arr, n):
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = (arr[i], 0)

		def func(i, j):
			if dp[i][j]:
				return dp[i][j]
			(f1, s1) = func(i + 1, j)
			a1 = s1 + arr[i]
			(f2, s2) = func(i, j - 1)
			a2 = s2 + arr[j]
			if a1 > a2:
				f = a1
				s = f1
			else:
				f = a2
				s = f2
			dp[i][j] = (f, s)
			return dp[i][j]
		(f, s) = func(0, n - 1)
		return f


class Solution:

	def util(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		first = arr[i] + min(self.util(arr, i + 2, j, dp), self.util(arr, i + 1, j - 1, dp))
		last = arr[j] + min(self.util(arr, i + 1, j - 1, dp), self.util(arr, i, j - 2, dp))
		dp[i][j] = max(first, last)
		return dp[i][j]

	def optimalStrategyOfGame(self, arr, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return self.util(arr, 0, n - 1, dp)


class Solution:

	def optimalStrategyOfGame(self, array, n):
		result = self.solve(array, n)
		return result

	def solve(self, array, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		for i in range(n):
			dp[i][i] = array[i]
		for g in range(n):
			(i, j) = (0, g)
			while j < n:
				if g == 0:
					dp[i][j] = array[i]
				elif g == 1:
					dp[i][j] = max(array[i], array[j])
				else:
					tempI = array[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					tempJ = array[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
					dp[i][j] = max(tempI, tempJ)
				i += 1
				j += 1
		return dp[0][n - 1]


class Solution:

	def optimalStrategyOfGame(self, array, n):
		result = self.solve(array, n)
		return result

	def solve(self, array, n):
		dpPlus0 = [0 for j in range(n)]
		dpPlus1 = [0 for j in range(n)]
		dpPlus2 = [0 for j in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if i > j:
					continue
				pickingI = array[i] + min(dpPlus2[j], dpPlus1[j - 1])
				pickingJ = array[j] + min(dpPlus1[j - 1], dpPlus0[j - 2])
				dpPlus0[j] = max(pickingI, pickingJ)
			dpPlus2 = dpPlus1.copy()
			dpPlus1 = dpPlus0.copy()
		return dpPlus0[n - 1]


class Solution:

	def optimalStrategyOfGame(self, array, n):
		result = self.solve(array, n)
		return result

	def solve(self, array, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if i > j:
					continue
				hold1 = 0 if i + 2 >= n else dp[i + 2][j]
				hold2 = 0 if i + 1 >= n else dp[i + 1][j - 1]
				tempI = array[i] + min(hold1, hold2)
				hold1 = 0 if i + 1 >= n else dp[i + 1][j - 1]
				hold2 = 0 if i >= n else dp[i][j - 2]
				tempJ = array[j] + min(hold1, hold2)
				dp[i][j] = max(tempI, tempJ)
		return dp[0][n - 1]