Problem:
 Score : 100 points    Problem Statement Taro and Jiro will play the following game against each other.  Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N) .
Until a becomes empty, the two players perform the following operation alternately, starting from Taro:   Remove the element at the beginning or the end of a . The player earns x points, where x is the removed element.   Let X and Y be Taro's and Jiro's total score at the end of the game, respectively.
Taro tries to maximize X - Y , while Jiro tries to minimize X - Y .  Assuming that the two players play optimally, find the resulting value of X - Y .      Constraints  All values in input are integers.  1 \leq N \leq 3000  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  \ldots  a_N       Output Print the resulting value of X - Y , assuming that the two players play optimally.        Sample Input 1 4
10 80 90 30      Sample Output 1 10  The game proceeds as follows when the two players play optimally (the element being removed is written bold):   Taro: (10, 80, 90, 30 ) → (10, 80, 90)  Jiro: (10, 80, 90 ) → (10, 80)  Taro: (10, 80 ) → (10)  Jiro: ( 10 ) → ()   Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100 .       Sample Input 2 3
10 100 10      Sample Output 2 -80  The game proceeds, for example, as follows when the two players play optimally:   Taro: ( 10 , 100, 10) → (100, 10)  Jiro: ( 100 , 10) → (10)  Taro: ( 10 ) → ()   Here, X = 10 + 10 = 20 and Y = 100 .       Sample Input 3 1
10      Sample Output 3 10       Sample Input 4 10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1      Sample Output 4 4999999995  The answer may not fit into a 32-bit integer type.       Sample Input 5 6
4 2 9 7 1 5      Sample Output 5 2  The game proceeds, for example, as follows when the two players play optimally:   Taro: (4, 2, 9, 7, 1, 5 ) → (4, 2, 9, 7, 1)  Jiro: ( 4 , 2, 9, 7, 1) → (2, 9, 7, 1)  Taro: (2, 9, 7, 1 ) → (2, 9, 7)  Jiro: (2, 9, 7 ) → (2, 9)  Taro: (2, 9 ) → (2)  Jiro: ( 2 ) → ()   Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13 .

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])

main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
 
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print(dp[0][n - 1])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp=[]
    for i in range(n):
    	dp.append([0] * n)
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print(dp[0][n - 1])
main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print(dp[0][n - 1])
main()

Solution (Python):
n = int(input())
a = tuple(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def calc():
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp

dp = calc()
print(dp[0][n - 1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
a = [int(x) for x in input().split()]

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int, input().split()))

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if n%2 ==0:
        dp[i][i]=-s[i]
        turn =0
    else:
        dp[i][i]=s[i]
        turn = 1
def findMax(i,j):
    dp[i][j] = max(dp[i+1][j]+s[i],dp[i][j-1]+s[j])
def findMin(i,j):
    dp[i][j]= min(dp[i+1][j]-s[i],dp[i][j-1]-s[j])
for length in range(2,n+1):
    for j in range(n-length+1):
        if not turn:
            findMax(j,j+length-1)
        else:
            findMin(j,j+length-1)
    turn^=1

print(dp[0][n-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Solution (Python):
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]
 
 
n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])

Solution (Python):
MAX_INT = 100

N = int(input())
a = list(map(int,input().split()))

dp = [[0]*(N) for i in range(N+1)]

if  N%2 == 0:
  hand = 0
else:
  hand = 1

for i in range(N):
  if hand == 0:
    dp[i][i] = -a[i]
  else:
    dp[i][i] = a[i]
  
for i in range(1,N+1):
  for j in range(N+1):
    if i+j < N:
      if (hand+i)%2 == 1: 
        dp[j][i+j] = max(dp[j][i+j-1]+a[i+j],dp[j+1][i+j]+a[j])
      else:
        dp[j][i+j] = min(dp[j][i+j-1]-a[i+j],dp[j+1][i+j]-a[j])
    else:
      break  
print(dp[0][-1])

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
A = LI()

acc = [0]*(N+1)
for i in range(N):
    acc[i+1] = acc[i] + A[i]

dp = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    dp[i][i+1] = A[i]


for l in range(N)[::-1]:
    for r in range(l+1, N+1):
        dp[l][r] = max((acc[r]-acc[l+1])-dp[l+1][r]+A[l], (acc[r-1]-acc[l]-dp[l][r-1]+A[r-1]))

print(2*dp[0][N]-acc[-1])

Solution (Python):
N=int(input())
A=list(map(int,input().strip().split(' ')))
MAx=max(A)
dp=[[-3*max(A)]*N for i in range(N)]
for i in range(N):
    dp[i][i]=A[i]

for length in range(2,len(A)+1):
    for start in range(0,len(A)-length+1):
        left=start
        right=start+length-1
        temp1=0
        temp2=0
        dp[left][right]=max(A[left]-dp[left+1][right],A[right]-dp[left][right-1])
print(dp[0][-1])

Solution (Python):


import sys

class LDeque:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = a[i]
            for j in range(i + 1, n):
                dp[i][j] = max(a[i] - dp[i + 1][j], -dp[i][j - 1] + a[j])

        print(dp[0][n - 1])

solver = LDeque()
input = sys.stdin.readline

solver.solve()

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for _ in range(N)]


for n in range(N):
	for i in range(N - n):
		if n == 0:
			dp[n][i] = a[i]
		else:
			dp[n][i] = max(a[i] - dp[n - 1][i + 1], a[i + n] - dp[n - 1][i])
			
print(dp[N - 1][0])

Solution (Python):
import fileinput


def deque_score(item_list):
    player_a_scores = [0] * (len(item_list) * len(item_list))
    player_b_scores = [0] * (len(item_list) * len(item_list))

    for gap in range(len(item_list)):
        for li in range(len(item_list) - gap):

            if gap == 0:
                player_a_scores[li + len(item_list) * li] = item_list[li]
                player_b_scores[li + len(item_list) * li] = -item_list[li]
            else:
                ri = li + gap
                player_a_scores[li + len(item_list) * ri] = max(
                    item_list[li] + player_b_scores[(li + 1) + len(item_list) * ri],
                    item_list[ri] + player_b_scores[li + len(item_list) * (ri - 1)]
                )

                player_b_scores[li + len(item_list) * ri] = min(
                    player_a_scores[(li + 1) + len(item_list) * ri] - item_list[li],
                    player_a_scores[li + len(item_list) * (ri - 1)] - item_list[ri]
                )
    return player_a_scores[len(item_list) * (len(item_list) - 1)]


inp = fileinput.FileInput()
inp.readline()

item_list = [int(v) for v in inp.readline().split(" ")]
print(deque_score(item_list))

Solution (Python):
N = int(input())
a = list(map(int,input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(i, N):
        dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])

print(dp[0][N-1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(N-i+1):
        dp[i][j] = max(-dp[i-1][j] + A[j+i-1], -dp[i-1][j+1] + A[j])
print(dp[-1][0])

Solution (Python):




n = int(input())
aa = [int(i) for i in input().split()]

INF = 10**13




dp= [[0]*(i+1) for i in range(n+1)]

"""
for b in range(n,-1,-1):
    for a in range(b+1):


        c=(n-a-b)%2
        if c:
            if b<n and a>0:
                dp[b][a] = max(dp[b+1][a] + aa[b], dp[b][a-1]+aa[a-1])
            elif b<n:
                dp[b][a] = dp[b+1][a] + aa[b]
            elif a>0:
                dp[b][a] = dp[b][a-1]+aa[a-1]
        else:
            if b<n and a>0:
                dp[b][a] = min(dp[b+1][a] - aa[b], dp[b][a-1]-aa[a-1])
            elif b<n:
                dp[b][a] = dp[b+1][a] - aa[b]
            elif a>0:
                dp[b][a] = dp[b][a-1] - aa[a-1]

print(dp)
for b in range(1,n+1):
    for a in range(b-1,-1,-1):

        c=(n-a-b)%2
        if c:
            dp[b][a] = max(dp[b-1][a], dp[b][a+1])
        else:
            dp[b][a] = min(dp[b-1][a], dp[b][a+1])
"""

for b in range(1,n+1):
    for a in range(b-1,-1,-1):

        c=(n-a-b+1)%2
        if c:
            dp[b][a] = max(dp[b-1][a]+aa[b-1], dp[b][a+1]+aa[a])
        else:
            dp[b][a] = min(dp[b-1][a]-aa[b-1], dp[b][a+1]-aa[a])


print(dp[n][0])

Solution (Python):
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Solution (Python):
n=int(input())
v=list(map(int, input().split()))
dp=[[-1] * n for i in range(n)]
def f(a, b):
    if a > b:
        return 0
    elif a == b:
        return v[a]
    elif dp[a][b] == -1:
        c1 = v[a] + min(f(a + 2, b), f(a + 1, b - 1))
        c2 = v[b] + min(f(a, b - 2), f(a + 1, b - 1))
        dp[a][b] = max(c1, c2)
    return dp[a][b]

print(2*f(0, n-1) - sum(v))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = a[i]
for l in range(1, n):
    for s in range(n - l):
        dp[s][s + l] = max(a[s] - dp[s + 1][s + l], a[s + l] - dp[s][s + l - 1])
print(dp[0][n - 1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

dp = [[0 for _ in range(N)] for _ in range(N)]

for index in range(N):
    dp[index][index] = A[index]

for i in range(N - 2, -1, -1):
    for j in range(i + 1, N):
        l = A[i] - dp[i+1][j]
        r = A[j] - dp[i][j-1]
        dp[i][j] = max(l,r)

print(dp[0][N-1])

Solution (Python):
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Solution (Python):
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
for k in range(1, N + 1):
    for l in range(N - k + 1):
        r = l + k
        if (N - k) % 2 == 0:
            dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])
        else:
            dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

print(dp[0][N])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

dp = [[0]*(n+1) for i in range(n+1)]
for l in range(1,n+1):
    for i in range(n+1-l):
        j = i+l
        if (n-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
print(dp[0][-1])

Solution (Python):
import sys

input = sys.stdin.readline

def chmax(a, b):
    if a >= b:
        return a
    return b

def chmin(a, b):
    if a <= b:
        return a
    return b

def main():
    N = int(input())
    a = list(map(int, input().split()))

    
    
    
    dp = [[0] * (N+2)  for _ in range(N+2)]

    for len in range(1, N + 1):
        for i in range(N + 1 - len):
            j = i + len

            if (N - len) % 2 == 0:
                dp[i][j] = chmax(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = chmin(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][N])

main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

dp = [[0 for _ in range(n)] for _ in range(n)]

m = n % 2

if m == 0:
    for i in range(n):
        dp[i][i] = -a[i]
else:
    for i in range(n):
        dp[i][i] = a[i]

for i in range(1, n):
    for x in range(n-i):
        y = x + i
        if i % 2 == m:
            dp[x][y] = min(dp[x+1][y] - a[x], dp[x][y-1] - a[y])
        else:
            dp[x][y] = max(dp[x + 1][y] + a[x], dp[x][y - 1] + a[y])

print(dp[0][n-1])

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
A=tuple(map(int,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
for j in range(1,n+1):
    for i in range(n-j+1):
        DP[j][i]=max(A[i]-DP[j-1][i+1],A[i+j-1]-DP[j-1][i])
print(DP[n][0])

Solution (Python):


import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            
    return(dp[0][-1])

n = int(input()) 
a = list(map(int, input().split()))
print(f(n, a))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    B()

Solution (Python):
def fun(i,j):
	
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))

for i in range(n-1,-1,-1):
	for j in range(i,n,1):
		if i==j:
			dp[i][j]=arr[i]
		else:
			dp[i][j]=max(arr[i]-dp[i+1][j],arr[j]-dp[i][j-1])
		
print(dp[0][n-1])

Solution (Python):
def fun(i,j):
	
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))
print(2*fun(0,n-1)-sum(arr))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))

dp = [[0]*n for i in range(n)]
if n %2 == 0:
    for i in range(n):
        dp[i][i] = -a[i]
else:
    for i in range(n):
        dp[i][i] = a[i]

for i in range(1,n):
    for j in range(n-i):
        if (n-i)%2 == 1:
            dp[j][i+j] = max(dp[j][i+j-1]+a[i+j],dp[j+1][i+j]+a[j])
        else:
            dp[j][i+j] = min(dp[j][i+j-1]-a[i+j],dp[j+1][i+j]-a[j])
print(dp[0][n-1])

Solution (Python):

import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*(n+1) for j in range(n+1)]


for i in range(n):
  dp[0][i] = 0

for j in range(1,n+1):
  for i in range(n):
    if i+j <= n:
      dp[j][i] = max(a[i]-dp[j-1][i+1],a[i+j-1]-dp[j-1][i])
print(dp[n][0])

Solution (Python):
import sys
N = int(input())
a = list(map(int,input().split(" ")))

dp = [ [0]*N  for _ in range(N) ]

for l in range(N-1,-1,-1):
    for r in range(l,N):
        turn = ((N - r) + l + 1) % 2

        if turn == 0:
            if r > 0 and l < N-1:
                dp[l][r] = max(a[l] + dp[l+1][r],a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] =  a[l] + dp[l+1][r]
            else:
                dp[l][r] =  a[r] + dp[l][r-1]
        else:
            if r > 0 and l < N-1:
                dp[l][r] = min(-a[l] + dp[l+1][r],-a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] = -a[l] + dp[l+1][r]
            else:
                dp[l][r] = -a[r] + dp[l][r-1]
print(dp[0][N-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]
for w in range(1, n):
    for l in range(n - w):
        dp[l][l+w] = max(a[l] - dp[l+1][l+w], a[l+w] - dp[l][l+w-1])
print(dp[0][n-1])

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

print(DP[0][n-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(1, n+1):
    for i in range(n - l + 1):
        j = i + l
        if (n - l) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][n])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

dp = [[0]*(n+1) for _ in range(n+1)]

for length in range(1,n+1):
    for stidx in range(n-length+1):
        
        if(n-length)%2:
            dp[stidx][stidx+length] = min(dp[stidx+1][stidx+length] - a[stidx],
                                          dp[stidx][stidx+length-1] - a[stidx+length-1])
        
        else:
            dp[stidx][stidx+length] = max(dp[stidx+1][stidx+length] + a[stidx],
                                          dp[stidx][stidx+length-1] + a[stidx+length-1])
            
print(dp[0][n])

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
dp = [[0] * (N+1) for _ in range(N+1)]

for d in range(N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l] * (-1)**(N+d+1)
            
        else:
            s = (-1)**(N+d+1)
            dp[l][r] = max(A[l] + dp[l+1][r] * s, A[r] + dp[l][r-1] * s) * s

print(dp[0][N-1])

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * N for _ in range(N+1)]
    dp[1] = A
    for length in range(2, N+1):
        for idx in range(N - length + 1):
            dp[length][idx] = max(A[idx] - dp[length-1][idx+1],
                                  A[idx+length-1] - dp[length-1][idx])
    print(dp[N][0])


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
input = stdin.readline

N = int(input())
a = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for j in range(2, N + 1):
    for i in range(0, N + 1 - j):
        
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i],
                               dp[i][i + j - 1] - a[i + j - 1])

print(dp[0][N])

Solution (Python):
from sys import stdin
input = stdin.readline

N = int(input())
a = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for j in range(2, N + 1):
    for i in range(0, N + 1 - j):
        
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i],
                               dp[i][i + j - 1] - a[i + j - 1])

print(dp[0][N])

Solution (Python):
N = int(input())
a_list = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for l in range(N + 1 - i):
        r = l + i
        dp[l][r] = max(a_list[l] - dp[l+1][r], a_list[r-1] - dp[l][r-1])

print(dp[0][N])

Solution (Python):
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
B=[[0 for x in range(N+1)] for y in range(N)]
for i in range(N):
    B[i][i+1]=A[i]
for l in range(1,N):
    for i in range( N-l):
        B[i][i+l+1]=max(A[i]-B[i+1][i+l+1], A[i+l] - B[i][i+l]  )
print B[0][N]

Solution (Python):


n = input()
a = map(int, raw_input().split())
oo = sum(a) + 1

dp_max = [[-oo] * n for _ in range(n)]
dp_min = [[oo] * n for _ in range(n)]

for i in range(n):
    dp_max[i][i] = a[i]
    dp_min[i][i] = -a[i]

for i in range(1, n):
    for j in range(n - i):
        k = i + j
        dp_max[j][k] = max(dp_min[j + 1][k] + a[j], dp_min[j][k - 1] + a[k])
        dp_min[j][k] = min(dp_max[j + 1][k] - a[j], dp_max[j][k - 1] - a[k])
print(dp_max[0][n - 1])

Solution (Python):



N = int(input())

A = tuple(map(int, input().split()))

dp = [ [0]*(N+1) for _ in range(N+1)]
for d in range(1,N+1):
    for l in range(N+1-d):
        r = l+d
        dp[l][r] = \
        max(
            A[l] - dp[l+1][r],
            A[r-1] - dp[l][r-1]
                )
print(dp[0][N])

Solution (Python):



N = int(input())
A = list(map(int, input().split()))

dp = [ [0]*(N+1) for _ in range(N+1)]
for d in range(1,N+1):
    for l in range(N+1-d):
        r = l+d
        dp[l][r] = \
        max(
            A[l] - dp[l+1][r],
            A[r-1] - dp[l][r-1]
                )
print(dp[0][N])