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 solve():
    n = int(input())
    a = tuple(int(x) for x in input().split())

    memo = tuple([None] * n for _ in range(n))
    for i, aa in enumerate(a):
        memo[i][i] = aa

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

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


if __name__ == '__main__':
    solve()

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

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

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

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

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

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

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

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

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(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)

Solution (Python):
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 range(N-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 = [int(i) for i in 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+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][N])

Solution (Python):
from numpy import*
n,a=open(0)
n=int(n)
a=int64(a.split())
dp=zeros((n+1,n+1),'i8')
for k in range(1,n+1):
    i=arange(n-k+1)
    j=i+k
    dp[i,j]=amin(vstack((dp[i+1,j]-a[i],dp[i,j-1]-a[j-1])),0)if(n-k)%2else amax(vstack((dp[i+1,j]+a[i],dp[i,j-1]+a[j-1])),0)
print(dp[0,n])

Solution (Python):
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for k in range(1,n+1):
    for i in range(n-k+1):
        j=i+k
        dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])if(n-k)%2else max(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
print(dp[0][n])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
A = [int(x) for x in input().split()]

"""
・x < M > y → x+y-Mに取り替える
・V字型に帰着
・貪欲

"""

B = deque() 
for a in A:
    B.append(a)
    while True:
        if len(B) < 3:
            break
        x,y,z = B[-3], B[-2], B[-1]
        if x <= y >= z:
            B.pop()
            B.pop()
            B[-1] = x + z - y
            continue
        break

pts = [0,0]
player = 0
while B:
    if B[0] > B[-1]:
        pts[player] += B[0]
        B.popleft()
    else:
        pts[player] += B[-1]
        B.pop()
    player ^= 1

answer = pts[0] - pts[1]
print(answer)

Solution (Python):
n,a=int(input()),list(map(int,input().split()));dp=[[None]*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][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])

Solution (Python):
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_float(n):
    return list(map(float, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    for i in range(len(dp)):
        dp[i][i] = a[i]
    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    return dp[0][n - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()], dtype=np.int64)

s = np.copy(a)
for i in range(1, n):
    s = np.maximum(a[:n-i]-s[1:n-i+1], a[i:]-s[:n-i])

print(s[0])