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.



Sample input:
4
10 80 90 30


Sample output:
10

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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: # sente

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

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

print(dp[0][n])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# dp[j][i]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
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])

Submission status: Accepted

Solution code:
# n=int(input())
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
		# print(i,j)
		# if(i<=j):
		if(i==j):
			x=a[i]
			y=-a[i]
			mat[i][j]=(x,y)
		else:
			# print(i+1)
			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])
# print(mat)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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

Submission status: Accepted

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

dp = [[0]*n for _ in range(n)]
# dp[i][j] : 残っている石がi からj の時の手番から見た終了得点の最大値

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[0]*(N+1) for _ in range(N+1)] # 初期値を対角成分だけ0、その他をfloat("inf")にすると1000ms程度遅くなる

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをi+shift_iに書き換えてshift_iについてループ
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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[0]*(N+1) for _ in range(N+1)] # 初期値を対角成分だけ0、その他をfloat("inf")にすると1000ms程度遅くなる

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをshift_iと書き換えてループ
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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをshift_iと書き換えてループ
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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[0]*(N+1) for _ in range(N+1)]

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをshift_iと書き換えてループ
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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

# dp[i][j] 区間a[i,j)だけ残った時点で互いの点数を一旦0とし、ゲームを最後まで続けた場合のX-Yの値
dp = [[0]*(N+1) for _ in range(N+1)]

# こちらもメモ化再帰ではpypy3でも間に合わない
# j==i+1, i+2, ...とループしてdpテーブルの上三角部分を対角線と平行に埋めていく。jをshift_iと書き換えてループ
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#dp=[[ for i in range(3000)] for j in range(3000)]
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])

Submission status: Accepted

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

# dp[l][r]: 区間[l,r)のときのX-Y
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

# 終局から遡る
# tは系列の長さ
for t in range(1, N+1):
    for l in range(N-t+1):
        r = t + l
        # 減った石の個数が偶数のとき、先手
        if (N - t) % 2 == 0:
            # 先手は直前の状態が大きい方
            # +X する
            dp[l][r] = max(dp[l + 1][r] + A[l], dp[l][r - 1] + A[r-1])
        else:
            # 先手は直前の状態が小さい方
            # -Y する
            dp[l][r] = min(dp[l + 1][r] - A[l], dp[l][r - 1] - A[r-1])

print(dp[0][N])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
#import random
#N = 3000
#A = [random.randint(1, 10**9) for _ in range(N)]


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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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]の加算結果を与えれば             |
    |    右辺の式はすべて符号反転するので－側の最小を目指すというのと         |
    |        ＋の最大を目指すというのを満たすのでその区間における            |
    |           プレイヤーの最善スコアが出る                               |
    ====================================================================|

"""

#solve
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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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[:]
    # print (dp2)
    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])
            # print (dp2)
        else:
            # print (dp2[k - 1:N], A[k - 1:], dp2[k:], A[: N - k])
            dp1[k:] = np.maximum(dp2[k - 1:N] + A[k - 1:], dp2[k:] + A[:N - k + 1])
            # print (dp1)
    print (dp1[N])

else:
    dp1[1:] = A[:]
    # print (dp1)
    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])
            # print (dp2)
        else:
            # print (dp2[k - 1:N], A[k - 1:], dp2[k:], A[: N - k])
            dp1[k:] = np.maximum(dp2[k - 1:N] + A[k - 1:], dp2[k:] + A[:N - k + 1])
            # print (dp1)
    print (dp1[N])

Submission status: Accepted

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

# dp[i][j]: a[i], a[j] の選択肢があるとき、その後に蓄積されるX-Yの最大値
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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])
# print(dp)

Submission status: Accepted

Solution code:
N = int(input())
arr = [int(i) for i in input().split()]
tot = sum(arr)
mem = [[0]* N for i in range(N)]
# updating bottom 2 rows
# mem[N-2][j] 
# mem[N-1][N-1]
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])

  # updating leftmost cols
  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)
  #print(mem)
  tmp = tot - mem[0][N-1]
  ans = mem[0][N-1] - tmp
  print("%s" % ans)

Submission status: Accepted

Solution code:
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
#import numpy as np
#import sympy as syp(素因数分解とか)
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(): #startline--------------------------------------------
    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() #endline===============================================

Submission status: Accepted

Solution code:
#L

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)]#[l,r)の範囲が残っているときに取れる最大値

for i in range(1,N+1):#r-lの値
    for j in range(N):#lの値
        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] )

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://scrapbox.io/ganariya/AtCoderDP%E3%81%BE%E3%81%A8%E3%82%81%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88_L%E5%95%8F%E9%A1%8C_%E3%80%8CDeque%E3%80%8D

from collections import deque
N = int(input())
a = deque(list(map(int,input().split())))
#区間dp
#dp[i][j] : [i,j)番目の要素が残っている状態からの最適解

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

print(dp[0][N])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()  # n
    a = [int(x) for x in input().split()]
    return deque(a)


print(main())

Submission status: Accepted

Solution code:
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()  # n
    a = [int(x) for x in input().split()]
    return deque(a)


print(main())