Given a row of n coins of values arr[1], arr[2], ... arr[n], where n is even. Geek plays a game against an opponent by alternating turns. 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. Determine the maximum possible amount geek can get if he moves first.
Note: Both of them play optimally
Example 1:
Input: N = 4, arr[] = {5, 3, 7, 10}
Output: 15
Explanation: 
Geek chooses 10.
Opponent chooses 7.
Geek chooses 5.
Opponent chooses 3.
Example 2:
Input: N = 4, arr[] = {8, 15, 3, 7}
Output: 22
Explanation: 
Geek chooses 7.
Opponent chooses 8.
Geek chooses 15.
Opponent chooses 3.
Your Task:  
You don't need to read input or print anything. Complete the function maxAmount() which takes N  and array arr as input parameter and returns the maximum value geek can get.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
2 ≤ N ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def maxAmount(self, A, N):
		# code here

Solutions:
class Solution:

	def maxAmount(self, arr, N):
		n = len(arr)
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = arr[i]
		for i in range(n - 1):
			dp[i][i + 1] = max(arr[i], arr[i + 1])
		for k in range(2, n):
			for i in range(n - k):
				j = i + k
				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 maxAmount(self, A, N):
		dp = [[0 for i in range(N)] for j in range(N)]
		for gap in range(N):
			for i in range(N - gap):
				j = i + gap
				if i == j:
					dp[i][j] = A[i]
				elif i + 1 == j:
					dp[i][j] = max(A[i], A[j])
				else:
					dp[i][j] = max(A[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), A[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
		return dp[0][N - 1]


class Solution:

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

	def maxAmount(self, arr, n):
		dp = dict()
		return self.util(n, 0, n - 1, arr, dp)


class Solution:

	def recur(self, A, i, j, dp):
		if i == j:
			d[i][j] = A[i]
		if dp[i][j] != -1:
			return dp[i][j]
		if i + 1 == j:
			dp[i][j] = max(A[i], A[j])
			return dp[i][j]
		start = A[i] + min(self.recur(A, i + 2, j, dp), self.recur(A, i + 1, j - 1, dp))
		end = A[j] + min(self.recur(A, i, j - 2, dp), self.recur(A, i + 1, j - 1, dp))
		dp[i][j] = max(start, end)
		return dp[i][j]

	def maxAmount(self, A, N):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		return self.recur(A, 0, N - 1, dp)


class Solution:

	def maxAmount(self, a, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g
			while i < n and j < n:
				if g == 0:
					dp[i][j] = a[i]
				elif g == 1:
					dp[i][j] = max(a[i], a[j])
				else:
					z = a[i] + min(dp[i + 1][j - 1], dp[i + 2][j])
					x = a[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
					dp[i][j] = max(z, x)
				i = i + 1
				j = j + 1
		return dp[0][n - 1]


class Solution:

	def maxAmount(self, arr, N):
		dp = [[0] * 1005 for i in range(1005)]
		for i in range(N - 1, -1, -1):
			for j in range(0, N):
				if i == j:
					dp[i][j] = arr[i]
					continue
				if i > j:
					continue
				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]))
		return dp[0][N - 1]


class Solution:

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

	def maxAmount(self, A, N):
		self.dp = [[-1 for i in range(N + 1)] for i in range(N + 1)]
		return self.solve(0, N - 1, A)


class Solution:

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

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


class Solution:

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

		def solve(i, j, dp, v):
			if i == j and v:
				return a[i]
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if v:
				dp[i][j] = max(a[i] + solve(i + 1, j, dp, False), a[j] + solve(i, j - 1, dp, False))
			else:
				dp[i][j] = min(solve(i + 1, j, dp, True), solve(i, j - 1, dp, True))
			return dp[i][j]
		return solve(0, n - 1, dp, True)


class Solution:

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

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


class Solution:

	def maxAmount(self, arr, N):
		dp = [[0] * N for i in range(N)]
		for i in range(N):
			dp[i][i] = arr[i]
		for gap in range(1, N):
			i = 0
			while i + gap < N:
				j = i + gap
				dp[i][j] = max(arr[i] - dp[i + 1][j], arr[j] - dp[i][j - 1])
				i = i + 1
		return (sum(arr) + dp[0][N - 1]) // 2


class Solution:

	def maxAmount(self, A, N):

		def recursive(A, i, j):
			if i == j:
				return A[i]
			elif j == i + 1:
				return max(A[i], A[j])
			else:
				res_a = A[i] + min(recursive(A, i + 2, j), recursive(A, i + 1, j - 1))
				res_b = A[j] + min(recursive(A, i, j - 2), recursive(A, i + 1, j - 1))
				return max(res_a, res_b)
		dp = [[-1] * (len(A) + 1) for _ in range(len(A) + 1)]

		def memoize(A, i, j):
			nonlocal dp
			if i == j:
				return A[i]
			elif j == i + 1:
				return max(A[i], A[j])
			if dp[i][j] != -1:
				return dp[i][j]
			else:
				res_a = A[i] + min(memoize(A, i + 2, j), memoize(A, i + 1, j - 1))
				res_b = A[j] + min(memoize(A, i, j - 2), memoize(A, i + 1, j - 1))
				dp[i][j] = max(res_a, res_b)
				return dp[i][j]
		return memoize(A, 0, N - 1)


class Solution:

	def rec(self, arr, i, j):
		if i > j or i >= len(arr) or j < 0:
			return 0
		lv = arr[i] + min(self.rec(arr, i + 2, j), self.rec(arr, i + 1, j - 1))
		rv = arr[j] + min(self.rec(arr, i, j - 2), self.rec(arr, i + 1, j - 1))
		return max(lv, rv)

	def mem(self, 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]
		lv = arr[i] + min(self.mem(arr, i + 2, j, dp), self.mem(arr, i + 1, j - 1, dp))
		rv = arr[j] + min(self.mem(arr, i + 1, j - 1, dp), self.mem(arr, i, j - 2, dp))
		dp[i][j] = max(lv, rv)
		return dp[i][j]

	def maxAmount(self, A, N):
		return self.mem(A, 0, N - 1, [[-1 for _ in range(N)] for _ in range(N)])
		return self.rec(A, 0, N - 1)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		Arr = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.maxAmount(Arr, N)
		print(ans)


class Solution:

	def maxAmount(self, A, N):
		memo = {}
		return self.maxSum(A, 0, N - 1, memo)

	def maxSum(self, A, i, j, memo):
		k = (i, j)
		if k in memo:
			return memo[k]
		if i == j - 1:
			return max(A[i], A[j])
		else:
			lhs = A[i]
			rhs = A[j]
			lhs += min(self.maxSum(A, i + 2, j, memo), self.maxSum(A, i + 1, j - 1, memo))
			rhs += min(self.maxSum(A, i + 1, j - 1, memo), self.maxSum(A, i, j - 2, memo))
			memo[k] = max(rhs, lhs)
			return memo[k]


class Solution:

	def maxAmount(self, A, N):
		dp = [[[0, 0] for i in range(N)] for j in range(N)]
		arr = A[:]
		dp[0][0] = [A[0], 0]
		for i in range(1, N):
			arr[i] += arr[i - 1]
			dp[i][i] = [A[i], 0]
		col = 0
		while col < N:
			col += 1
			for row in range(N - col):
				(L, R) = (row, row + col)
				m1 = A[L] + dp[L + 1][R][1]
				m2 = A[R] + dp[L][R - 1][1]
				x = max(m1, m2)
				dp[L][R] = [x, arr[R] - arr[L] + A[L] - x]
		return dp[0][-1][0]


class Solution:

	def maxAmount(self, A, N):

		def find_max(A, l, r, count):
			if count == N // 2:
				return 0
			if dp[l][r] != -1:
				return dp[l][r]
			left = A[l] + min(find_max(A, l + 2, r, count + 1), find_max(A, l + 1, r - 1, count + 1))
			right = A[r] + min(find_max(A, l, r - 2, count + 1), find_max(A, l + 1, r - 1, count + 1))
			dp[l][r] = max(left, right)
			return max(left, right)
		dp = [[-1] * N for _ in range(N)]
		return find_max(A, 0, len(A) - 1, 0)


class Solution:

	def maxAmount(self, A, N):

		def helper(arr, i, j, n, dp):
			if j < 0 or i >= n:
				return 0
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = max(arr[i] + min(helper(arr, i + 2, j, n, dp), helper(arr, i + 1, j - 1, n, dp)), arr[j] + min(helper(arr, i, j - 2, n, dp), helper(arr, i + 1, j - 1, n, dp)))
			return dp[i][j]
		dp = [[-1 for j in range(N)] for i in range(N)]
		return helper(A, 0, N - 1, N, dp)


class Solution:

	def maxAmount(self, A, N):
		dp = []
		for i in range(N):
			dp.append([[0, 0] for j in range(N)])
		for i in range(N):
			dp[i][i] = [A[i], 0]
		temp = 1
		while temp < N:
			i = 0
			j = temp
			while i < N and j < N:
				if A[i] + dp[i + 1][j][1] >= A[j] + dp[i][j - 1][1]:
					dp[i][j][0] = A[i] + dp[i + 1][j][1]
					dp[i][j][1] = dp[i + 1][j][0]
				else:
					dp[i][j][0] = A[j] + dp[i][j - 1][1]
					dp[i][j][1] = dp[i][j - 1][0]
				i += 1
				j += 1
			temp += 1
		return dp[0][-1][0]


class Solution:

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


class Solution:

	def maxAmount(self, A, 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(A[i] + min(x, y), A[j] + min(y, z))
		return table[0][N - 1]


class Solution:

	def maxAmount(self, A, N):
		dp = [[-1] * N for i in range(N)]
		return self.go(0, N - 1, A, N, dp)

	def go(self, s, e, A, N, dp):
		if s > e:
			return 0
		if dp[s][e] != -1:
			return dp[s][e]
		compute = self.go(s + 1, e - 1, A, N, dp)
		frst = A[s] + min(compute, self.go(s + 2, e, A, N, dp))
		last = A[e] + min(compute, self.go(s, e - 2, A, N, dp))
		dp[s][e] = max(frst, last)
		return dp[s][e]


class Solution:

	def maxAmount(self, arr, n):
		dp = {}

		def helper(i, j):
			if i > j or i >= n or j < 0:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			a = arr[i] + min(helper(i + 2, j), helper(i + 1, j - 1))
			b = arr[j] + min(helper(i + 1, j - 1), helper(i, j - 2))
			res = max(a, b)
			dp[i, j] = res
			return res
		return helper(0, n - 1)


class Solution:

	def maxAmount(self, nums, N):
		mymap = dict()

		def dfs(i, j):
			if (i, j) in mymap:
				return mymap[i, j]
			if i >= len(nums) or j < 0:
				return 0
			if i == j:
				return nums[i]
			if i > j:
				return 0
			mymap[i, j] = max(nums[i] + min(dfs(i + 2, j), dfs(i + 1, j - 1)), nums[j] + min(dfs(i + 1, j - 1), dfs(i, j - 2)))
			return mymap[i, j]
		return dfs(0, len(nums) - 1)


def optimalSt(arr, i, j, dp):
	if i == j:
		return arr[i]
	if i == j - 1:
		return max(arr[i], arr[j])
	elif dp[i][j] != -1:
		return dp[i][j]
	else:
		left = arr[i] + min(optimalSt(arr, i + 1, j - 1, dp), optimalSt(arr, i + 2, j, dp))
		right = arr[j] + min(optimalSt(arr, i + 1, j - 1, dp), optimalSt(arr, i, j - 2, dp))
		dp[i][j] = max(left, right)
		return dp[i][j]

class Solution:

	def maxAmount(self, A, N):
		dp = [[-1 for i in range(N)] for j in range(N)]
		return optimalSt(A, 0, N - 1, dp)


class Solution:

	def maxAmount(self, A, N):
		dp = []
		for i in range(N):
			temp = [0] * N
			dp.append(temp)
		for i in range(N - 1):
			dp[i][i + 1] = max(A[i], A[i + 1])
		for gap in range(3, N, 2):
			for i in range(0, N - gap):
				j = i + gap
				dp[i][j] = max(A[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), A[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
		return dp[0][N - 1]


class Solution:

	def maxAmount(self, A, N):
		arr = [[0 for _ in range(N)] for _ in range(N)]
		if N & 1:
			for i in range(N):
				arr[i][i] = A[i]
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				if j - i + 1 & 1 ^ N & 1:
					arr[i][j] = min(arr[i + 1][j], arr[i][j - 1])
				else:
					arr[i][j] = max(A[i] + arr[i + 1][j], A[j] + arr[i][j - 1])
		return arr[0][N - 1]


class Solution:

	def advantage(self, A, s, e, g):
		if s == e:
			if g:
				return (A[s], A[s])
			else:
				return (A[s], 0)
		if self.d.get((s, e, g)):
			return self.d[s, e, g]
		(foa, fgs) = self.advantage(A, s + 1, e, not g)
		use_first = A[s] - foa
		(loa, lgs) = self.advantage(A, s, e - 1, not g)
		use_last = A[e] - loa
		if use_first > use_last:
			if g:
				gs = A[s] + fgs
			else:
				gs = fgs
			self.d[s, e, g] = (use_first, gs)
			return (use_first, gs)
		else:
			if g:
				gs = A[e] + lgs
			else:
				gs = lgs
			self.d[s, e, g] = (use_last, gs)
			return (use_last, gs)

	def maxAmount(self, A, N):
		self.d = dict()
		(geek_advantage, geek_score) = self.advantage(A, 0, N - 1, True)
		return geek_score


class Solution:

	def maxAmount(self, A, N):
		dp = [[0 for i in range(N)] for i in range(N)]
		for L in range(N):
			for i in range(N - L):
				j = i + L
				if L == 0:
					dp[i][j] = A[i]
				elif L == 1:
					dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
				else:
					val1 = A[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					val2 = A[j] + min(dp[i][j - 2], dp[i + 1][j - 1])
					dp[i][j] = max(val1, val2)
		return dp[0][-1]