Two players X and Y are playing a game in which there are pots of gold arranged in a line, each containing some gold coins. They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to maximize the number of coins collected by X, assuming Y also plays optimally.
Return the maximum coins X could get while playing the game. Initially, X starts the game.
Example 1:
Input:
N = 4
Q[] = {8, 15, 3, 7}
Output: 22
Explanation: Player X starts and picks 7. Player Y 
picks the pot containing 8. Player X picks the pot
containing 15. Player Y picks 3.
Total coins collected by X = 7 + 15 = 22.
Example 2:
Input:
N = 4
A[] = {2, 2, 2, 2}
Output: 4 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes an integer N and an array of size N  as input and returns the maximum coins collected by player X.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 <= N <= 500
1 <= A[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Game theory

Starter code: class Solution:

    def maxCoins(self,arr, n):

        # Code here

        

 

Solutions:
class Solution:

	def maxCoins(self, arr, n):
		n = len(arr)
		memo = [[-1] * n for _ in range(n)]

		def calculate_coins(start, end, is_x_turn):
			if start == end:
				if is_x_turn:
					return arr[start]
				else:
					return 0
			if memo[start][end] != -1:
				return memo[start][end]
			if is_x_turn:
				choose_left = arr[start] + calculate_coins(start + 1, end, False)
				choose_right = arr[end] + calculate_coins(start, end - 1, False)
				max_coins = max(choose_left, choose_right)
			else:
				choose_left = calculate_coins(start + 1, end, True)
				choose_right = calculate_coins(start, end - 1, True)
				max_coins = min(choose_left, choose_right)
			memo[start][end] = max_coins
			return max_coins
		max_coins = calculate_coins(0, n - 1, True)
		return max_coins


class Solution:

	def maxCoins(self, coin, n):
		if not coin:
			return 0
		dp = [[-1] * n for _ in range(n)]
		return optimal_strategy(coin, 0, n - 1, dp)

def optimal_strategy(coin, i, j, dp):
	if i == j:
		return coin[i]
	if i + 1 == j:
		return max(coin[i], coin[j])
	if dp[i][j] == -1:
		start = coin[i] + min(optimal_strategy(coin, i + 2, j, dp), optimal_strategy(coin, i + 1, j - 1, dp))
		end = coin[j] + min(optimal_strategy(coin, i + 1, j - 1, dp), optimal_strategy(coin, i, j - 2, dp))
		dp[i][j] = max(start, end)
	return dp[i][j]


class Solution:

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

		def fun(i, j, sum1):
			if i + 1 == j:
				return max(arr[i], arr[j])
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = max(sum1 - fun(i + 1, j, sum1 - arr[i]), sum1 - fun(i, j - 1, sum1 - arr[j]))
			return dp[i][j]
		return fun(0, n - 1, sum(arr))


class Solution:

	def maxCoins(self, arr, 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
				x = 0
				if i + 2 <= j:
					x = dp[i + 2][j]
				y = 0
				if i + 1 <= j - 1:
					y = dp[i + 1][j - 1]
				z = 0
				if i <= j - 2:
					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 count(self, i, j, arr, dp):
		if i == j:
			return arr[i]
		if i + 1 == j:
			return max(arr[i], arr[j])
		if dp[i][j] == 0:
			start = arr[i] + min(self.count(i + 2, j, arr, dp), self.count(i + 1, j - 1, arr, dp))
			end = arr[j] + min(self.count(i + 1, j - 1, arr, dp), self.count(i, j - 2, arr, dp))
			dp[i][j] = max(start, end)
		return dp[i][j]

	def maxCoins(self, arr, n):
		try:
			dp = [[0 for _ in range(n)] for _ in range(n)]
			return self.count(0, n - 1, arr, dp)
		except Exception as e:
			print('e', dir(e), cause(e))


class Solution:

	def maxCoins(self, arr, n):
		lookup = [[0] * n for i in range(n)]

		def findmaxcoins(arr, i, j, lookup):
			if i == j:
				return arr[i]
			if i + 1 == j:
				return max(arr[i], arr[j])
			if lookup[i][j] == 0:
				start = arr[i] + min(findmaxcoins(arr, i + 1, j - 1, lookup), findmaxcoins(arr, i + 2, j, lookup))
				end = arr[j] + min(findmaxcoins(arr, i + 1, j - 1, lookup), findmaxcoins(arr, i, j - 2, lookup))
				lookup[i][j] = max(start, end)
			return lookup[i][j]
		return findmaxcoins(arr, 0, n - 1, lookup)


class Solution:

	def maxCoins(self, arr, n):

		def solve(start, end):
			if start > end:
				return 0
			if dp[start][end] != -1:
				return dp[start][end]
			a = arr[start] + min(solve(start + 2, end), solve(start + 1, end - 1))
			b = arr[end] + min(solve(start + 1, end - 1), solve(start, end - 2))
			dp[start][end] = max(a, b)
			return dp[start][end]
		dp = [[-1 for j in range(0, n)] for i in range(0, n)]
		return solve(0, n - 1)


class Solution:

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

		def solve(i, j, dp, c):
			if i > j:
				return 0
			if i == j and c:
				return arr[i]
			if dp[i][j] != -1:
				return dp[i][j]
			if c:
				dp[i][j] = max(arr[i] + solve(i + 1, j, dp, False), arr[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]
		dp[0][n - 1] = solve(0, n - 1, dp, True)
		return dp[0][n - 1]


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for j in range(n + 2)] for i 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 + 1, n):
				if i + 1 == j:
					dp[i][j] = max(arr[i:j + 1])
					continue
				a1 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
				a2 = arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1])
				dp[i][j] = max(a1, a2)
		return dp[0][n - 1]


class Solution:

	def maxCoins(self, arr, n):

		def calculate(T, i, j):
			return T[i][j] if i <= j else 0

		def findMaxCoins(coin):
			n = len(coin)
			if n == 1:
				return coin[0]
			if n == 2:
				return max(coin[0], coin[1])
			T = [[0 for x in range(n)] for y in range(n)]
			for iteration in range(n):
				i = 0
				j = iteration
				while j < n:
					start = coin[i] + min(calculate(T, i + 2, j), calculate(T, i + 1, j - 1))
					end = coin[j] + min(calculate(T, i + 1, j - 1), calculate(T, i, j - 2))
					T[i][j] = max(start, end)
					i = i + 1
					j = j + 1
			return T[0][n - 1]
		return findMaxCoins(arr)


class Solution:

	def gold(self, l, r, arr, dp):
		if l > r:
			return 0
		if (l, r) in dp:
			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 maxCoins(self, arr, n):
		dp = {}
		return self.gold(0, n - 1, arr, dp)


class Solution:

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

		def dfs(nums, i, j, dp):
			if i == j:
				return nums[i]
			if i + 1 == j:
				return max(nums[i], nums[j])
			if dp[i][j] == 0:
				start = nums[i] + min(dfs(nums, i + 2, j, dp), dfs(nums, i + 1, j - 1, dp))
				end = nums[j] + min(dfs(nums, i, j - 2, dp), dfs(nums, i + 1, j - 1, dp))
				dp[i][j] = max(start, end)
			return dp[i][j]
		return dfs(arr, 0, n - 1, dp)


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

class Solution:

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


class Solution:

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

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


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0] * (n + 2) 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(n):
				if i < j:
					dp[i][j] = max(arr[i] + min(dp[i + 1][j - 1], dp[i + 2][j]), arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1]))
		return dp[0][n - 1]


class Solution:

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

		def recursive(arr, lt=0, rt=len(arr) - 1, flag=0):
			if lt > rt:
				return 0
			if dp[lt][rt][flag] != -1:
				return dp[lt][rt][flag]
			if flag == 0:
				a = arr[lt] + recursive(arr, lt + 1, rt, 1)
				b = arr[rt] + recursive(arr, lt, rt - 1, 1)
				dp[lt][rt][flag] = max(a, b)
			else:
				a = recursive(arr, lt + 1, rt, 0)
				b = recursive(arr, lt, rt - 1, 0)
				dp[lt][rt][flag] = min(a, b)
			return dp[lt][rt][flag]
		return recursive(arr)


class Solution:

	def maxCoins(self, arr, n):

		def dfs(arr, i, j, turn, d):
			if i > j:
				return 0
			if d.get((i, j, turn)) != None:
				return d[i, j, turn]
			if turn == 1:
				d[i, j, turn] = max(arr[i] + dfs(arr, i + 1, j, 2, d), arr[j] + dfs(arr, i, j - 1, 2, d))
				return d[i, j, turn]
			if turn == 2:
				d[i, j, turn] = min(dfs(arr, i + 1, j, 1, d), dfs(arr, i, j - 1, 1, d))
				return d[i, j, turn]
		d = dict()
		return dfs(arr, 0, n - 1, 1, d)


def solve(arr, i, j):
	global dp
	if i == j:
		return arr[i]
	if i + 1 == j:
		return max(arr[i], arr[j])
	if dp[i][j] != -1:
		return dp[i][j]
	start = arr[i] + min(solve(arr, i + 2, j), solve(arr, i + 1, j - 1))
	end = arr[j] + min(solve(arr, i + 1, j - 1), solve(arr, i, j - 2))
	dp[i][j] = max(start, end)
	return dp[i][j]

class Solution:

	def maxCoins(self, arr, n):
		global dp
		dp = [[-1] * (n + 1) for i in range(n + 1)]
		return solve(arr, 0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		t = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n:
				if i + 2 <= j:
					x = t[i + 2][j]
				else:
					x = 0
				if i + 1 <= j - 1:
					y = t[i + 1][j - 1]
				else:
					y = 0
				if i <= j - 2:
					z = t[i][j - 2]
				else:
					z = 0
				t[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
				i += 1
				j += 1
		return t[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for i in range(0, n + 3)] for i in range(0, n + 3)]
		t = [0 for i in range(0, n + 3)]
		for i in range(0, n):
			t[i + 1] = arr[i]
		for i in range(1, n + 1):
			dp[i][i] = t[i]
		for i in range(1, n):
			dp[i][i + 1] = max(t[i], t[i + 1])
		for i in range(n + 1, 0, -1):
			for j in range(i, n + 1):
				if i == j or j == i + 1:
					continue
				op1 = t[i] + min(dp[i + 1][j - 1], dp[i + 2][j])
				op2 = t[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
				dp[i][j] = max(op1, op2)
		return dp[1][n]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, coins, 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:
					dp[i][j] = coins[i]
				elif i + 1 == j:
					dp[i][j] = max(coins[i], coins[j])
				elif i < j:
					dp[i][j] = max(coins[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), coins[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
		return dp[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

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

		def dfs(s, e):
			if s == e:
				return arr[s]
			if s + 1 == e:
				return max(arr[s], arr[e])
			if dp[s][e] != 0:
				return dp[s][e]
			start = arr[s] + min(dfs(s + 2, e), dfs(s + 1, e - 1))
			end = arr[e] + min(dfs(s + 1, e - 1), dfs(s, e - 2))
			dp[s][e] = max(start, end)
			return dp[s][e]
		return dfs(0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g + i
			while j < n:
				if g == 0:
					dp[i][j] = arr[i]
				elif g == 1:
					dp[i][j] = max(arr[i], arr[j])
				else:
					op1 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					op2 = arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1])
					dp[i][j] = max(op1, op2)
				i += 1
				j += 1
		return dp[0][-1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, nums, n):

		def dfs(coin, i, j):
			if i == j:
				return coin[i]
			if i + 1 == j:
				return max(coin[i], coin[j])
			if dp[i][j] == 0:
				start = coin[i] + min(dfs(coin, i + 2, j), dfs(coin, i + 1, j - 1))
				end = coin[j] + min(dfs(coin, i + 1, j - 1), dfs(coin, i, j - 2))
				dp[i][j] = max(start, end)
			return dp[i][j]
		dp = [[0 for x in range(len(nums))] for y in range(len(nums))]
		return dfs(nums, 0, len(nums) - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):

		def dp(arr, i, j, p1, p2, fg, dic):
			if len(arr) <= 0:
				return 0
			if (i, j, fg) in dic:
				return dic[i, j, fg]
			if fg == 0:
				x = dp(arr[1:], i + 1, j, p1, p2, 1, dic) + arr[0]
				y = dp(arr[:-1], i, j - 1, p1, p2, 1, dic) + arr[-1]
				ans = max(x, y)
			elif fg == 1:
				x = dp(arr[1:], i + 1, j, p1, p2, 0, dic)
				y = dp(arr[:-1], i, j - 1, p1, p2, 0, dic)
				ans = min(x, y)
			dic[i, j, fg] = ans
			return ans
		return dp(arr, 0, n, 0, 0, 0, {})
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, a, n):
		if n == 1:
			return a[0]
		elif n == 2:
			return max(a)
		t = []
		for i in range(len(a) + 2):
			temp = []
			for j in range(len(a) + 2):
				temp.append(-1)
			t.append(temp)

		def function(a, i, j):
			if t[i][j] != -1:
				return t[i][j]
			if i > j:
				t[i][j] = 0
				return 0
			p = a[i] + min(function(a, i + 2, j), function(a, i + 1, j - 1))
			q = a[j] + min(function(a, i + 1, j - 1), function(a, i, j - 2))
			t[i][j] = max(p, q)
			return t[i][j]
		return function(a, 0, len(a) - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):

		def max_val(i, arr, j, dic):
			if i > j:
				return 0
			key = str(i) + ',' + str(j)
			if key not in dic:
				val1 = arr[i] + min(max_val(i + 2, arr, j, dic), max_val(i + 1, arr, j - 1, dic))
				val2 = arr[j] + min(max_val(i + 1, arr, j - 1, dic), max_val(i, arr, j - 2, dic))
				dic[key] = max(val1, val2)
			return dic[key]
		dic = {}
		v = max_val(0, arr, n - 1, dic)
		return v
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):

		def solve(nums, dp, s, e):
			if s > e:
				dp[s][e] = 0
			if s == e:
				dp[s][e] = nums[s]
			if dp[s][e] != -1:
				return dp[s][e]
			l = nums[s] + min(solve(nums, dp, s + 2, e), solve(nums, dp, s + 1, e - 1))
			r = nums[e] + min(solve(nums, dp, s + 1, e - 1), solve(nums, dp, s, e - 2))
			dp[s][e] = max(l, r)
			return dp[s][e]
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return solve(arr, dp, 0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


def rec(dp, l, r, arr):
	if l > r:
		return 0
	if dp[l][r] != -1:
		return dp[l][r]
	le = arr[l] + min(rec(dp, l + 2, r, arr), rec(dp, l + 1, r - 1, arr))
	ri = arr[r] + min(rec(dp, l + 1, r - 1, arr), rec(dp, l, r - 2, arr))
	ans = max(le, ri)
	dp[l][r] = ans
	return ans

class Solution:

	def maxCoins(self, arr, n):
		dp = [[-1 for x in range(n)] for y in range(n)]
		return rec(dp, 0, n - 1, arr)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dpf = [[0 for x in range(n)] for y in range(n)]
		dps = [[0 for x in range(n)] for y in range(n)]
		for i in range(n):
			for j in range(i, -1, -1):
				if i == j:
					dpf[i][j] = arr[i]
				elif j + 1 == i:
					dpf[j][i] = max(arr[j], arr[i])
					dps[j][i] = min(arr[j], arr[i])
				else:
					dpf[j][i] = max(arr[i] + dps[j][i - 1], arr[j] + dps[j + 1][i])
					dps[j][i] = min(dpf[j][i - 1], dpf[j + 1][i])
		return dpf[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


from functools import lru_cache

class Solution:

	def maxCoins(self, arr, n):

		@lru_cache(None)
		def max_coin(i, j):
			if i > j:
				return 0
			if i == j:
				return arr[i]
			x = min(max_coin(i + 2, j), max_coin(i + 1, j - 1)) + arr[i]
			y = min(max_coin(i + 1, j - 1), max_coin(i, j - 2)) + arr[j]
			return max(x, y)
		return max_coin(0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		return play(arr, 0, n - 1, dict())

def play(arr, a, b, memo):
	m = (a, b)
	if m in memo:
		return memo[m]
	if b - a == 1:
		memo[m] = max(arr[a], arr[b])
		return memo[m]
	if b == a:
		memo[m] = arr[a]
		return memo[m]
	y_gain_a = play(arr, a + 1, b, memo)
	y_gain_b = play(arr, a, b - 1, memo)
	x_gain_a = arr[a] + min(play(arr, a + 2, b, memo), play(arr, a + 1, b - 1, memo))
	x_gain_b = arr[b] + min(play(arr, a, b - 2, memo), play(arr, a + 1, b - 1, memo))
	if x_gain_a - y_gain_a > x_gain_b - y_gain_b:
		memo[m] = x_gain_a
	else:
		memo[m] = x_gain_b
	return memo[m]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dp = [[(0, 0)] * (n + 1) for _ in range(n + 1)]
		for window_size in range(1, n + 1):
			for i in range(1, n + 1):
				j = i + window_size - 1
				if j > n:
					break
				if window_size == 1:
					dp[i][j] = (arr[i - 1], 0)
				else:
					option1 = arr[i - 1] + dp[i + 1][j][1]
					option2 = arr[j - 1] + dp[i][j - 1][1]
					if option1 > option2:
						dp[i][j] = (option1, dp[i + 1][j][0])
					else:
						dp[i][j] = (option2, dp[i][j - 1][0])
		return dp[1][n][0]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def pick(self, arr, i, j):
		if i == j:
			return arr[i]
		if i + 1 == j:
			return max(arr[i], arr[j])
		start = arr[i] + min(self.pick(arr, i + 2, j), self.pick(arr, i + 1, j - 1))
		end = arr[j] + min(self.pick(arr, i + 1, j - 1), self.pick(arr, i, j - 2))
		return max(start, end)

	def maxCoins_rec(self, arr, n):
		return self.pick(arr, 0, n - 1)

	def calculate(self, T, i, j):
		return T[i][j] if i <= j else 0

	def maxCoins(self, coin, n):
		if n == 1:
			return coin[0]
		if n == 2:
			return max(coin[0], coin[1])
		T = [[0 for x in range(n)] for y in range(n)]
		for iteration in range(n):
			i = 0
			j = iteration
			while j < n:
				start = coin[i] + min(self.calculate(T, i + 2, j), self.calculate(T, i + 1, j - 1))
				end = coin[j] + min(self.calculate(T, i + 1, j - 1), self.calculate(T, i, j - 2))
				T[i][j] = max(start, end)
				i = i + 1
				j = j + 1
		return T[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def helper(self, arr, i, j):
		if i > j:
			return 0
		if i == j:
			return arr[i]
		if (i, j) in self.memo:
			return self.memo[i, j]
		option1 = arr[i] + min(self.helper(arr, i + 2, j), self.helper(arr, i + 1, j - 1))
		option2 = arr[j] + min(self.helper(arr, i, j - 2), self.helper(arr, i + 1, j - 1))
		self.memo[i, j] = max(option1, option2)
		return self.memo[i, j]

	def maxCoins(self, arr, n):
		self.memo = {}
		return self.helper(arr, 0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

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

	def util(self, i, j, arr, dp):
		if i > j:
			return 0
		if i == j:
			return arr[i]
		if dp[i][j] != 0:
			return dp[i][j]
		left = arr[i] + min(self.util(i + 2, j, arr, dp), self.util(i + 1, j - 1, arr, dp))
		right = arr[j] + min(self.util(i + 1, j - 1, arr, dp), self.util(i, j - 2, arr, dp))
		dp[i][j] = max(left, right)
		return dp[i][j]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


from functools import lru_cache

class Solution:

	def maxCoins(self, arr, n):

		@lru_cache(None)
		def max_coin(i, j):
			if i == j:
				return (arr[i], 0)
			(f1, s1) = max_coin(i + 1, j)
			(f2, s2) = max_coin(i, j - 1)
			x = arr[i] + s1
			y = arr[j] + s2
			if x > y:
				return (x, f1)
			else:
				return (y, f2)
		return max_coin(0, n - 1)[0]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


from copy import deepcopy

class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = arr[i]
		i = 1
		while i < n:
			j = 0
			k = i
			while k < n:
				if k - j == 1:
					dp[j][k] = max(arr[j], arr[k])
				else:
					start = arr[j] + min(dp[j + 2][k], dp[j + 1][k - 1])
					end = arr[k] + min(dp[j][k - 2], dp[j + 1][k - 1])
					dp[j][k] = max(start, end)
				j += 1
				k += 1
			i += 1
		return dp[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for i in range(n)] for i in range(n)]
		i = j = 0
		while i < n:
			dp[i][j] = arr[i]
			i += 1
			j += 1
		(i, j) = (0, 1)
		while j < n:
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
			i += 1
			j += 1
		for a in range(2, n):
			i = 0
			j = a
			while j < n:
				v1 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
				v2 = arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1])
				dp[i][j] = max(v1, v2)
				i += 1
				j += 1
		return dp[0][-1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):

		def max_coin(i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				return (arr[i], 0)
			(f1, s1) = max_coin(i + 1, j)
			(f2, s2) = max_coin(i, j - 1)
			x = arr[i] + s1
			y = arr[j] + s2
			if x > y:
				dp[i][j] = (x, f1)
			else:
				dp[i][j] = (y, f2)
			return dp[i][j]
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
		return max_coin(0, n - 1)[0]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


from functools import lru_cache

class Solution:

	def maxCoins(self, arr, n):

		@lru_cache(None)
		def helper(left, right):
			if left == right:
				return (arr[left], 0)
			(num1, str1) = helper(left + 1, right)
			(num2, str2) = helper(left, right - 1)
			res1 = arr[left] + str1
			res2 = arr[right] + str2
			if res1 > res2:
				return (res1, num1)
			else:
				return (res2, num2)
		ans = helper(0, n - 1)
		return ans[0]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, nums, n):
		if len(nums) == 1:
			return nums[0]
		n = len(nums)
		dp = [[-1] * n for i in range(n)]

		def fun(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = nums[i]
				return dp[i][j]
			sc = max(nums[i] + min(fun(i + 2, j), fun(i + 1, j - 1)), nums[j] + min(fun(i, j - 2), fun(i + 1, j - 1)))
			dp[i][j] = sc
			return sc
		x = fun(0, n - 1)
		return x
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, arr, n):
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n):
			dp[i][i] = arr[i]
			if i < n - 1:
				dp[i][i + 1] = max(arr[i], arr[i + 1])
		gap = 2 if n % 2 == 1 else 3
		while gap < n:
			for i in range(n - gap):
				j = gap + i
				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]))
			gap = gap + 2
		return dp[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))


class Solution:

	def maxCoins(self, A, n):

		def _solve(l, r, actor):
			if dp[l][r] != [0, 0]:
				return dp[l][r].copy()
			L = _solve(l + 1, r, 1 - actor)
			L[actor] += A[l]
			R = _solve(l, r - 1, 1 - actor)
			R[actor] += A[r]
			dp[l][r] = ans = L if L[actor] >= R[actor] else R
			return ans.copy()
		dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
		last = 1 - n % 2
		for i in range(n):
			dp[i][i][last] = A[i]
		ans = _solve(0, n - 1, 0)
		return ans[0]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxCoins(arr, n))