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):
N = int(input())
A = list(map(int,input().split()))

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

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

for k in range(N-2,-1,-1):
    for l in range(k+1):
        r = k-l
        if k%2:
            dp[l][r] = min(dp[l+1][r] - A[l], dp[l][r+1] - A[-1-r])
        else:
            dp[l][r] = max(dp[l+1][r] + A[l], dp[l][r+1] + A[-1-r])

print(dp[0][0])

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

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):

    if i==j:
        SCORE[i][j]=0
        return
        
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k

    if l==1:
        SCORE[i][j]=max(SCORE[i+1][j]+A[i],SCORE[i][j-1]+A[j-1])-k

    else:
        SCORE[i][j]=min(SCORE[i+1][j]-A[i],SCORE[i][j-1]-A[j-1])-k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])

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

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):
    
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    t = [[0]*n for _ in range(n)]
    for i in range(n):
        t[i][i] = a[i]

    for i in range(n-2,-1,-1):
        z = t[i]
        y = t[i+1]
        for j in range(i+1,n):
            r = a[j] - z[j-1]
            u = a[i] - y[j]
            if r < u:
                r = u
            z[j] = r

    return t[0][-1]


print(main())

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,*A=map(int,open(0).read().split());r=range;S=[0]*-~N
for l in r(N):S=[max(S[i+1]+A[i],S[i]+A[i+l])if(l^N)&1else min(S[i+1]-A[i],S[i]-A[i+l])for i in r(N-l)]
print(S[0])

Solution (Python):
N,*A=map(int,open(0).read().split())
r=range
S=[0]*-~N
for l in r(N):
 S=[max(S[i+1]+A[i],S[i]+A[i+l])if(l^N)&1else min(S[i+1]-A[i],S[i]-A[i+l])for i in r(N-l)]
print(S[0])

Solution (Python):
N = int(input())
*A, = map(int, input().split())
t = (N & 1)
S = [0]*(N+1)
for l in range(1, N+1):
    S = [min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1)] if (l ^ N) & 1 else [max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1)]
print(S[0])

Solution (Python):
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(dp[N][0])

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

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 0
for j in range(1,n+1):
  for i in range(n+1-j):
    if (n-j) %2 == 0:
      dp[i][i+j] = max(dp[i+1][i+j] + a[i],dp[i][i+j-1]+a[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=[int(i) for i in input().split()]
dp=[[0]*(N+1) for i in range(N+1)]
for d in range(1,N+1):
  for i in range(N+1-d):
    if (N-d)%2==0:
      dp[i][i+d]=max(dp[i+1][i+d]+a[i],dp[i][i+d-1]+a[i+d-1])
    if (N-d)%2==1:
      dp[i][i+d]=min(dp[i+1][i+d],dp[i][i+d-1])
print(2*dp[0][N]-sum(a))

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

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

for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
S=[0]*(N+1)
for i in range(1,N+1):
    S[i]=S[i-1]+A[i-1]
dp=[[0]*N for i in range(N)]
for i in range(N):
    dp[i][i]=A[i]
for k in range(1,N):
    for i in range(N-k):
        j=i+k
        dp[i][j]=max(S[j]-S[i]-dp[i][j-1]+A[j],S[j+1]-S[i+1]-dp[i+1][j]+A[i])
print(2*dp[0][N-1]-S[N])

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