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 for i in range(N)] for j in range(N)]

    for i in range(N):
        dp[i][i] = a[i]

    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            right = a[i] - dp[i+1][j]
            left = a[j] - dp[i][j-1]
            if right > left:
                dp[i][j] = right
            else:
                dp[i][j] = left
    
    print(dp[0][N-1])


main()

Solution (Python):
N, *A = map(int, open(0).read().split())

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

print(dp[0][N])

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  
    a = [int(x) for x in readline().split()]  
    print(solve(N, a))


if __name__ == "__main__":
    main()

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


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

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

for length in range(1,n+1):
  for i in range(n+1):
    j=length+i
    if j<=i or j>n:continue
    if (n-length)%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 numpy as np

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

dp = np.zeros((N + 1, N + 1), dtype=np.int64)
for m in range(1, N + 1):
    if (N - m) % 2:
        dp[m][:N - m + 1] = np.minimum(dp[m - 1][1:N - m + 2] - A[:N - m + 1],
                                       dp[m - 1][:N - m + 1] - A[m - 1:])
    else:
        dp[m][:N - m + 1] = np.maximum(dp[m - 1][1:N - m + 2] + A[:N - m + 1],
                                       dp[m - 1][:N - m + 1] + A[m - 1:])

print(dp[N][0])

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

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

Solution (Python):


def submit():
    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 + 1):
        dp[i][i] = 0

    
    
    
    for l in range(1, n + 1):
        for i in range(n):
            j = i + l
            if j > n:
                break
            
            
            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])
            

submit()

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

Solution (Python):
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return map(int, data().split())
    out = sys.stdout.write
    

    n=int(data())
    A=list(mdata())
    dp=[[0]*n for i in range(n)]
    for i in range(n):
        dp[i][i]=A[i]
    for i in range(n):
        for j in range(i-1,-1,-1):
            dp[j][i]=max(A[j]-dp[j+1][i],A[i]-dp[j][i-1])
    print(dp[0][n-1])

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        j = i+l
        DP[i][j] = max(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 len in range(1,N+1):
    for i in range(0,N): 
        j=i+len 
        if j<=N:
            if (N-len)%2==0:
                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])
        else:
            break


    
    
        
    

print(DP[0][N])

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N-k):
            j = i+k
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i][j-1]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N):
            j = i+k
            if j>=N:
                continue
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i][j-1]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

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

sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print(2*dp[0][-1]-sa[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

N = int(input())
ali = list(map(int,input().split()))
inf = 10**15
dp = [[inf]*(N+1) for _ in range(N+1)]

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

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

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

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

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

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

for width in range(1, n + 1):
    for l in range(n + 1):
        r = width + l
        if r <= l or r > n:
            continue
        if (n - (r - l)) % 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, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = lambda: sys.stdin.readline().rstrip()

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


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


for gap in range(0, N):
    for left in range(N - gap):
        player = (N-gap-1) % 2
        right = left + gap

        if player == 0:
            if gap == 0:
                dp[left][right] = a[left]
                continue
            dp[left][right] = max(dp[left+1][right] + a[left], dp[left][right-1] + a[right])

        else:
            if gap == 0:
                dp[left][right] = -a[left]
                continue
            dp[left][right] = min(dp[left+1][right] - a[left], dp[left][right-1] - a[right])

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()


dp = list2d(N+1, N+1, 0)

for i in range(N):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        if turn == 0:
            dp[j][k] = -INF
        else:
            dp[j][k] = INF

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

for i in range(N-1, -1, -1):
    turn = i & 1
    for j in range(i+1):
        k = i - j
        l = j
        r = N - 1 - k
        if turn == 0:
            
            dp[j][k] = max(dp[j][k], dp[j+1][k] + A[l])
            dp[j][k] = max(dp[j][k], dp[j][k+1] + A[r])
        else:
            
            dp[j][k] = min(dp[j][k], dp[j+1][k] - A[l])
            dp[j][k] = min(dp[j][k], dp[j][k+1] - A[r])
ans = dp[0][0]
print(ans)

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):
    if n%2 == 1:
        dp[i][0] = a[i]
    else:
        dp[i][0] = -a[i]
for le in range(1,n):
    for i in range(n):
        if i + le >= n: continue
        if (n-le)%2 == 1:
            dp[i][le] = max(dp[i][le-1] + a[i+le], dp[i+1][le-1] + a[i])
        else:
            dp[i][le] = min(dp[i][le-1] - a[i+le], dp[i+1][le-1] - a[i])

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+1-j)] for j in range(n+1)]
for le in range(1,n+1):
    for i in range(n+1-le):
        if le%2==n%2:
            ret=dp[le-1][i]+a[i+le-1]
            if i+1<=n+1-le:
                ret=max(ret,dp[le-1][i+1]+a[i])
            dp[le][i]=ret
        else:
            ret=dp[le-1][i]-a[i+le-1]
            if i+1<=n+1-le:
                ret=min(ret,dp[le-1][i+1]-a[i])
            dp[le][i]=ret
print(dp[n][0])

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][i]=0

for l in range(1,n+1):
    for i in range(n+1):
        j=i+l
        if j>n:
            continue

        if (n-l)%2==0: 

            dp[i][j]= max(a[j-1]+dp[i][j-1],a[i]+dp[i+1][j])

        else: 
            dp[i][j]= min(-a[j-1]+dp[i][j-1],-a[i]+dp[i+1][j])

print(dp[0][n])

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

dpx=[[0 for i in range(0,N)] for i in range(0,N+1)]
dpy=[[0 for i in range(0,N)] for i in range(0,N+1)]

for i in range(1,N+1):
    for j in range(0,N):
        if N>j+i-1 and i!=1:
            dpx[i][j]=max(dpy[i-1][j+1]+A[j],dpy[i-1][j]+A[j+i-1])
            dpy[i][j]=min(dpx[i-1][j+1]-A[j],dpx[i-1][j]-A[j+i-1])
        elif N>j+i-1 and i==1:
            dpx[i][j]=A[j]
            dpy[i][j]=-A[j]

print(dpx[N][0])

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    dp=a[:]
    for i in range(1,n):
        for j in range(i-1,-1,-1):
            dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
    print(dp[0])
solve()

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    dp=a[:]
    for i in range(1,n):
        for j in range(i-1,-1,-1):
            dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
    print(dp[0])
solve()

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
dp=[0]*3000
for i in range(n):
    dp[i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[j]=max(a[i]-dp[j],a[j]-dp[j+1])
print(dp[0])

Solution (Python):

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*(i+1) for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
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[-1][0])

Solution (Python):

n=int(input())
a=list(map(int,input().split(" ")))
mat=[[(0,0) for i in range(n)] for j in range(n)]
for l in range(1,n+1):
	for i in range(n-l+1):
		j=i+l-1
		
		
		if(i==j):
			x=a[i]
			y=-a[i]
			mat[i][j]=(x,y)
		else:
			
			x=max(a[i]+mat[i+1][j][1],a[j]+mat[i][j-1][1])
			y=min(-a[i]+mat[i+1][j][0],-a[j]+mat[i][j-1][0])
			mat[i][j]=(x,y)
print(mat[0][n-1][0])

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





dp = []
for i in range(n):
    dp.append([-INF]*n)

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i == j:
            dp[i][j] = arr[i]
            continue
        dp[i][j] = max(arr[i] - dp[i+1][j], arr[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 i in range(N+1)]
for W in range(N):
    for l in range(N-W):
        r=l+W
        if (N-W+1)%2==0:
            dp[l][r]=max(a[l]+dp[l+1][r],dp[l][r-1]+a[r])
        else:
            dp[l][r]=min(dp[l+1][r]-a[l],dp[l][r-1]-a[r])
print(dp[0][N-1])

Solution (Python):
n = int(input())
A = list(map(int, 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):
        j = i+d
        if (n-d)%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 = [int(i) for i in input().split()]

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


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


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

print(2*dp[0][n]-sum(a))

Solution (Python):
from collections import deque
N = int(input())
a = list(map(int, input().split()))
dp = [[0]*N for i in range(N+1)]
if N%2 == 1:
    f = 1
else:
    f = -1
for i in range(1,N+1):
    for j in range(N-i+1):
        if f > 0:
            if j+1 < N:
                dp[i][j] = max(dp[i-1][j]+a[j+i-1], dp[i-1][j+1]+a[j])
            else:
                dp[i][j] = dp[i-1][j]+a[j+i-1]
        else:
            if j+1 < N:
                dp[i][j] = min(dp[i-1][j]-a[j+i-1], dp[i-1][j+1]-a[j])
            else:
                dp[i][j] = dp[i-1][j]-a[j+i-1]
    f *= -1
print(dp[N][0])

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

dp=[[-10**12]*(n+1) for i in range(n+1)]

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

Solution (Python):


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



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

for k in range(N):
    dp[k][k]=a[k]

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

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

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    dp = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = a[i]
    
    for i in range(N-1,-1,-1):
        for j in range(i,N):
            if dp[i][j] != -1:
                continue
            dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])
            
    print(dp[0][-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 j in range(1,n):
    for i in range(n-j):
        dp[i][i+j] = max(a[i]-dp[i+1][i+j], a[i+j]-dp[i][i+j-1])
print(dp[0][n-1])

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

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


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



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

print(dp[0][N])

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

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


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



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

print(dp[0][N])

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

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


dp = [[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0



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

print(dp[0][N])

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

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


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



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

print(dp[0][N])

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

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


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



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

print(dp[0][N])

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

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

dp = [[float("inf")]*(N+1) for _ in range(N+1)]

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

print(dp[0][N])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

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

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

		if (N-i)%2 == 0:  
			dp[j][k] = max(dp[j+1][k]+a[j], dp[j][k-1]+a[k-1])
		else:
			dp[j][k] = min(dp[j+1][k]-a[j], dp[j][k-1]-a[k-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(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][-1])

Solution (Python):
def solve(l, r, A, dp):
    if r - l < 2:
        return max(A[l:r + 1])

    x1 = dp[l + 2][r] if dp[l + 2][r] != -1 else solve(l + 2, r, A, dp)
    x2 = dp[l + 1][r - 1] if dp[l + 1][r - 1] != -1 else solve(l + 1, r - 1, A, dp)
    x3 = dp[l][r - 2] if dp[l][r - 2] != -1 else solve(l, r - 2, A, dp)

    dp[l][r] = max(min(x1, x2) + A[l], min(x2, x3) + A[r])

    return dp[l][r]


N = int(input())
A = [int(i) for i in input().split()]
dp = [[-1] * N for i in range(N)]
print(2*solve(0, N-1, A, dp)-sum(A))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 14
dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = inf
    else: dp[l][r] = -inf
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])

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]*3100 for _ in range(3100)]
for length in range(1,N+1):
    for i in range(N-length+1):
        j = i + length

        
        if (N-length)%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 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
  dp[i][i] = a[i-1]
for w in range(1,n):
  for i in range(1,n-w+1):
    j = i+w
    dp[i][j] = max(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)]

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

n=int(input())
A=list(int(i) for i in input().split())
dp=[[0 for i in range(n)] for j 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][-1])

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


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



for t in range(1, N+1):
    for l in range(N-t+1):
        r = t + l
        
        if (N - t) % 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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    N = int(input())
    a = list(map(int, input().split()))
    dp = [[0]*N for _ in range(N)]
    if N%2 == 0:
        for l in range(N-1, -1, -1):
            for r in range(N):
                if l > r:
                    continue
                if l==r==N-1 or l==r==0:
                    dp[l][N-r-1] = -a[l]
                if l+1==N or N-r-1+1==N:
                    continue
                if (r-l+1)%2 == 0:
                    dp[l][N-r-1] = max(dp[l+1][N-r-1]+a[l], dp[l][N-r-1+1]+a[r])
                else:
                    dp[l][N-r-1] = min(dp[l+1][N-r-1]-a[l], dp[l][N-r-1+1]-a[r])
    else:
        for l in range(N-1, -1, -1):
            for r in range(N):
                if l > r:
                    continue
                if l==r==N-1 or l==r==0:
                    dp[l][N-r-1] = a[l]
                if l+1==N or N-r-1+1==N:
                    continue
                if (r-l+1)%2 == 0:
                    dp[l][N-r-1] = min(dp[l+1][N-r-1]-a[l], dp[l][N-r-1+1]-a[r])
                else:
                    dp[l][N-r-1] = max(dp[l+1][N-r-1]+a[l], dp[l][N-r-1+1]+a[r])
    print(dp[0][0])
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys 
input = sys.stdin.readline
MOD = 10**9 +7
INF = 10**9

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    dp = [[0] * (n + 2)  for _ in range(n + 2)]
    
    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])

if __name__=='__main__':
    main()

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





dp = [[0] * (N+1) for _ in range(N+1)]
for g in range(N):
  for l in range(N-g):
    r = l + g
    n = r - l
    s = -1 if (N-n) % 2 == 0 else 1
    lv = dp[l+1][r] + s*A[l]
    rv = dp[l][r-1] + s*A[r]
    if s*lv > s*rv:
      dp[l][r] = lv
    else:
      dp[l][r] = rv

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

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

dp = [[None] * len(a) for _ in a]

for i in range(len(a)-1, -1, -1):
    for j in range(i, len(a)):
        if i == j:
            dp[i][j] = a[i]
            continue

        dp[i][j] = max(a[j] - dp[i][j-1], a[i] - dp[i+1][j])

print(dp[0][len(a) - 1])

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 ** 2

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


print(solve())