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):
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(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]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())

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

dp = [[0]*(N+1) for i 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] + a[l]
        dpr = -dp[l][r-1] + a[r-1]
        dp[l][r] = max(dpl,dpr)
print(dp[0][N])

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

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

for l in range(N):
    for i in range(N-l):
        if l == 0:
            dp[i][i] = a[i]
        else:
            j = i + l
            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
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]


















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

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

for i in range(n):
  dp[i][i] = nums[i]
  
for k in range(2, n+1):
  for l in range(n-k+1):
    r = l+k-1
    dp[l][r] = max(nums[l]-dp[l+1][r], nums[r] - dp[l][r-1])
    
print(dp[0][-1])

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

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_l
L - Deque / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
太郎君と次郎君が次のゲームで勝負します。
最初に、数列 a=(a1,a2,…,aN) が与えられます。 
a が空になるまで、二人は次の操作を交互に行います。 
先手は太郎君です。a の先頭要素または末尾要素を取り除く。 
取り除いた要素を x とすると、操作を行った人は x 点を得る。
ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 
太郎君は X−Y を最大化しようとし、次郎君は X−Y を最小化しようとします。

二人が最適に行動すると仮定したとき、X−Y を求めてください。

解説:
ただの区間DP
しかし、Pythonはカスなので工夫が必要
知見
    ====================================================================
    |dp[i][j]に-dp[i][j-1] or -dp[i+1][j]の加算結果を与えれば             |
    |    右辺の式はすべて符号反転するので－側の最小を目指すというのと         |
    |        ＋の最大を目指すというのを満たすのでその区間における            |
    |           プレイヤーの最善スコアが出る                               |
    ====================================================================|

"""


def solve():
    n = II()
    a = LI()
    dp = [[0]*n for i 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]
        ai = a[i]
        for j in range(i + 1, n):
            dpi[j] = max(ai-dpi1[j], a[j]-dpi[j-1])
    print(dp[0][n - 1])
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np

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

A = np.array(A, dtype = np.int64)
INF = 10 ** 12

dp1 = np.array([-INF] * (N + 1), dtype = np.int64)
dp2 = np.array([+INF] * (N + 1), dtype = np.int64)

if N % 2 == 0:
    dp2[1:] = -A[:]
    
    for k in range(2, N + 1):
        if k % 2 == 1:
            dp2[k:] = np.minimum(dp1[k - 1:N] - A[k - 1:], dp1[k:] - A[:N - k + 1])
            
        else:
            
            dp1[k:] = np.maximum(dp2[k - 1:N] + A[k - 1:], dp2[k:] + A[:N - k + 1])
            
    print (dp1[N])

else:
    dp1[1:] = A[:]
    
    for k in range(2, N + 1):
        if k % 2 == 0:
            dp2[k:] = np.minimum(dp1[k - 1:N] - A[k - 1:], dp1[k:] - A[:N - k + 1])
            
        else:
            
            dp1[k:] = np.maximum(dp2[k - 1:N] + A[k - 1:], dp2[k:] + A[:N - k + 1])
            
    print (dp1[N])

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

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] 
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] 

if N % 2 == 0: 
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        
    
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                
            
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                
            
    print (dp1[0][N])



else: 
    for i in range(N):
        dp1[i][i + 1] = A[i]
        
    
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                
            
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                
            
    print (dp1[0][N])

Solution (Python):

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


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

for i in range(N - 1, -1, -1):
  for j in range(i, N):
    if i == j:
      dp[i][j] = a[i]
    else:
      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, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for k in range(0,n-i+1):
    if (n-i) % 2 == 0:
      dp[k][k+i] = max(A[k] + dp[k+1][k+i], dp[k][k+i-1] + A[k+i-1])
    else:
      dp[k][k+i] = min(-A[k] + dp[k+1][k+i], dp[k][k+i-1] - A[k+i-1])
print(dp[0][n])

Solution (Python):
N = int(input())
arr = [int(i) for i in input().split()]
tot = sum(arr)
mem = [[0]* N for i in range(N)]



if N == 1:
  print("%s" % arr[0])
else:
  mem[N-1][N-1] = arr[N-1]
  mem[N-2][N-2] = arr[N-2]
  mem[N-2][N-1] = max(arr[N-2], arr[N-2])

  
  mem[0][0] = arr[0]
  mem[0][1] = max(arr[0], arr[1])
  mem[1][1] = arr[1]

  for i in range(N-3, -1, -1):
    for j in range(i, N):
      if i == 0 and j<=1 or i == 1 and j == 1:
        continue
      val1 = arr[i] + min(mem[i+1][j-1], mem[i+2][j])
      val2 = arr[j] + min(mem[i+1][j-1], mem[i][j-2])
      mem[i][j] = max(val1, val2)
  
  tmp = tot - mem[0][N-1]
  ans = mem[0][N-1] - tmp
  print("%s" % ans)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



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

    for i in reversed(range(n-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])

if __name__ == "__main__":
    main()

Solution (Python):


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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]

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

for i in range(1,N+1):
    for j in range(N):
        r=j+i
        if r>N:
            break
        l=j
        x=a[l]+(S[r]-S[l+1]) - dp[l+1][r]
        y=a[r-1]+(S[r-1]-S[l]) - dp[l][r-1]
        dp[l][r]=max(x,y)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[None]*n for _ in range(n)]
for d in range(n):
  for l in range(n-d):
    r = l + d
    if d:
      dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])
    else:
      dp[l][r] = a[l]
print(dp[0][n-1])

Solution (Python):
def main():
    n = int(input())
    *a, = map(int, input().split())

    memo = [[-1] * n for _ in range(n)]
    for i, x in enumerate(a):
        memo[i][i] = x

    for l in range(n - 1, -1, -1):  
        for r in range(l + 1, n):
            memo[l][r] = max(
                a[l] - memo[l + 1][r],
                a[r] - memo[l][r - 1]
            )

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


if __name__ == '__main__':
    main()

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):
import numpy as np
n=int(input())
A=np.array(list(map(int,input().split())),dtype='int64')
dp=A.copy()
for i in range(1,n):
    if i%2==0:
        dp=np.maximum(dp[1:]+A[:n-i],dp[:-1]+A[i:])
    else:
        dp=np.minimum(dp[1:]-A[:n-i],dp[:-1]-A[i:])
print(dp[0]*(n%2*2-1))

Solution (Python):


from collections import deque
N = int(input())
a = deque(list(map(int,input().split())))



def Sente(i,j):
    return True if (N-(j-i))%2 == 0 else False

dp = [[0]*(N+1) for _ in range(N+1)]
for i in reversed(range(N)):
    for j in range(i+1,N+1):
        if Sente(i,j):
            dp[i][j] = max(a[i] + dp[i+1][j], a[j-1] + dp[i][j-1])
        else:
            dp[i][j] = min(-a[i] + dp[i+1][j], -a[j-1] + dp[i][j-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 i in range(N - d + 1):
        j = i + d
        if (N-d) % 2 == 1:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
        else:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])

ans = dp[0][N]
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

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


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

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] = max(dp[i+1][j] + lst_a[i], dp[i][j-1] + lst_a[j-1])
		else :
			dp[i][j] = min(-lst_a[i] + dp[i + 1][j], -lst_a[j - 1]+dp[i][j - 1])


print(dp[0][N])

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

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

for i, a in enumerate(A):
  dp[i][i] = a

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

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

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
d = [0]*(N**2)
for i in range(N):
    for j in range(N-i):
        span = i*N+j
        if i == 0:
            d[span] = As[j]
        else:
            d[span] = max(As[j]-d[span-N+1], As[j+i]-d[span-N])
print(d[span])

Solution (Python):
def deque(a):
    n = len(a)
    cur = a[:]
    nxt = [0] * (n - 1)
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            nxt[i] = max(a[i] - cur[i + 1], a[j] - cur[i])
        cur, nxt = nxt, cur
    return cur[0]


def main():
    input()  
    a = [int(x) for x in input().split()]
    return deque(a)


print(main())

Solution (Python):
def deque(a):
    n = len(a)
    cur = [(x, 0) for x in a]
    nxt = [(0, 0)] * n
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            x, y = cur[i]
            z, t = cur[i + 1]
            if a[i] + t - z > a[j] + y - x:
                nxt[i] = (a[i] + t, z)
            else:
                nxt[i] = (a[j] + y, x)
        cur, nxt = nxt, cur
    return cur[0][0] - cur[0][1]


def main():
    input()  
    a = [int(x) for x in input().split()]
    return deque(a)


print(main())

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

score = [[(-1 if N % 2 == 0 else 1)*x for x in nums]]
for i in range(1, N):
    temp = []
    for j in range(N - i):
        func, sign = (min, -1) if i % 2 == N % 2 else (max, 1)
        temp.append(func(sign*nums[j] + score[-1][j + 1], sign*nums[j + i] + score[-1][j]))
    score.append(temp)

print(score[-1][-1])

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def japonska_gierka(): 
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    X = 0
    Y = 0
    wynik = [[None for i in range(N+1)] for j in range(N+1)]
    for dlugosc_kolejki in range(N+1):
        zabrano = N - dlugosc_kolejki
        for lewo in range(zabrano+1): 
            prawo = zabrano - lewo
            if dlugosc_kolejki == 0: 
                wynik[lewo][prawo] = 0 
            else:
                wynik[lewo][prawo] = max(A[lewo]-wynik[lewo+1][prawo], A[-prawo-1]-wynik[lewo][prawo+1])
    print(wynik[0][0])
    
japonska_gierka()

Solution (Python):

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


oe = N % 2








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

for i in range(N):
  
  
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]



for k in range(1, N):
  
  for i in range(0, N-k):
    
    
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    

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

Solution (Python):

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


oe = N % 2








score = [[None for _ in range(N)] for _ in range(N)]

for i in range(N):
  
  
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]



for k in range(1, N):
  
  for i in range(0, N-k):
    
    
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    

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

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

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

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

print(dp[0][n])

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][(n-1)-i] = a[i]

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

print(dp[0][0])

Solution (Python):

import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):

    dp = [[0]*N for _ in range(N)]
    for sub in range(N):
        turn = sub % 2
        for i in range(N-sub):
            j = i+sub
            
            if i == j:
                if (N-sub+1) % 2 == 0:
                    dp[i][i] = a[i]
                else:
                    dp[i][i] = -a[i]
                continue

            if (N-sub+1) % 2 == 0:    
                dp[i][j] = max(a[i] + dp[i+1][j], a[j]+dp[i][j-1])
            else:               
                dp[i][j] = min(-a[i] + dp[i+1][j], -a[j]+dp[i][j-1])
    print(dp[0][N-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, a)


if __name__ == '__main__':
    main()

Solution (Python):
def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-1, -1, -1):
        for r in range(l, n):
            if l == r:
                continue
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))

Solution (Python):
def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))

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

dp = [[0]*(n+1) for i in range(n+1) ]
for cnt in range(1, n+1):
    i = 0
    while True:
        j = i + cnt
        if j-1 >= n:
            break
        dp[i][j] = max(a[i] - dp[i+1][j], a[j-1] - dp[i][j-1])
        i += 1
print(dp[0][n])