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

main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [0] * (n*n)
    for i in range(n):
        dp[i+i*n] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i+j*n] = max(a[i] - dp[i + 1+j*n], a[j] - dp[i+(j - 1)*n])
    print(dp[(n - 1)*n])
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = tuple(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])

Submission status: Accepted

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

def calc():
    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])
    return dp

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

dp=[]
for i in range(n):
	dp.append([0]*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])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

dp=[]
for i in range(n):
	dp.append([0]*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])

Submission status: Accepted

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

dp=[]
for i in range(n):
	dp.append([0]*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])

Submission status: Accepted

Solution code:
def kukan(n, 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):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]
 
 
n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Submission status: Accepted

Solution code:
MAX_INT = 100

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

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

if  N%2 == 0:
  hand = 0
else:
  hand = 1

for i in range(N):
  if hand == 0:
    dp[i][i] = -a[i]
  else:
    dp[i][i] = a[i]
  
for i in range(1,N+1):
  for j in range(N+1):
    if i+j < N:
      if (hand+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])
    else:
      break  
print(dp[0][-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
A = LI()

acc = [0]*(N+1)
for i in range(N):
    acc[i+1] = acc[i] + A[i]

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


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

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().strip().split(' ')))
MAx=max(A)
dp=[[-3*max(A)]*N for i in range(N)]
for i in range(N):
    dp[i][i]=A[i]

for length in range(2,len(A)+1):
    for start in range(0,len(A)-length+1):
        left=start
        right=start+length-1
        temp1=0
        temp2=0
        dp[left][right]=max(A[left]-dp[left+1][right],A[right]-dp[left][right-1])
print(dp[0][-1])

Submission status: Accepted

Solution code:
# @author 

import sys

class LDeque:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = a[i]
            for j in range(i + 1, n):
                dp[i][j] = max(a[i] - dp[i + 1][j], -dp[i][j - 1] + a[j])

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

solver = LDeque()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for _ in range(N)]
#dp[n][i]...n+1:残った要素の個数、i:左端の要素が初期状態のi番目の要素、dp:X-Y

for n in range(N):
	for i in range(N - n):
		if n == 0:
			dp[n][i] = a[i]
		else:
			dp[n][i] = max(a[i] - dp[n - 1][i + 1], a[i + n] - dp[n - 1][i])
			
print(dp[N - 1][0])

Submission status: Accepted

Solution code:
import fileinput


def deque_score(item_list):
    player_a_scores = [0] * (len(item_list) * len(item_list))
    player_b_scores = [0] * (len(item_list) * len(item_list))

    for gap in range(len(item_list)):
        for li in range(len(item_list) - gap):

            if gap == 0:
                player_a_scores[li + len(item_list) * li] = item_list[li]
                player_b_scores[li + len(item_list) * li] = -item_list[li]
            else:
                ri = li + gap
                player_a_scores[li + len(item_list) * ri] = max(
                    item_list[li] + player_b_scores[(li + 1) + len(item_list) * ri],
                    item_list[ri] + player_b_scores[li + len(item_list) * (ri - 1)]
                )

                player_b_scores[li + len(item_list) * ri] = min(
                    player_a_scores[(li + 1) + len(item_list) * ri] - item_list[li],
                    player_a_scores[li + len(item_list) * (ri - 1)] - item_list[ri]
                )
    return player_a_scores[len(item_list) * (len(item_list) - 1)]


inp = fileinput.FileInput()
inp.readline()

item_list = [int(v) for v in inp.readline().split(" ")]
print(deque_score(item_list))

Submission status: Accepted

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

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

for i in range(N-1, -1, -1):
    for j in range(i, N):
        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:
N = int(input())
A = list(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


n = int(input())
aa = [int(i) for i in input().split()]

INF = 10**13
#from itertools import accumulate, product, permutations, combinations, groupby
#acc = accumulate([0]+aa)

#dp[x][y] = (bの位置x,aの」位置y)
dp= [[0]*(i+1) for i in range(n+1)]
#dp[n][0]=0
"""
for b in range(n,-1,-1):
    for a in range(b+1):
#        print(b,a)
#        print(dp)
        c=(n-a-b)%2
        if c:
            if b<n and a>0:
                dp[b][a] = max(dp[b+1][a] + aa[b], dp[b][a-1]+aa[a-1])
            elif b<n:
                dp[b][a] = dp[b+1][a] + aa[b]
            elif a>0:
                dp[b][a] = dp[b][a-1]+aa[a-1]
        else:
            if b<n and a>0:
                dp[b][a] = min(dp[b+1][a] - aa[b], dp[b][a-1]-aa[a-1])
            elif b<n:
                dp[b][a] = dp[b+1][a] - aa[b]
            elif a>0:
                dp[b][a] = dp[b][a-1] - aa[a-1]

print(dp)
for b in range(1,n+1):
    for a in range(b-1,-1,-1):
#        print(b,a)
        c=(n-a-b)%2
        if c:
            dp[b][a] = max(dp[b-1][a], dp[b][a+1])
        else:
            dp[b][a] = min(dp[b-1][a], dp[b][a+1])
"""

for b in range(1,n+1):
    for a in range(b-1,-1,-1):
#        print(b,a)
        c=(n-a-b+1)%2
        if c:
            dp[b][a] = max(dp[b-1][a]+aa[b-1], dp[b][a+1]+aa[a])
        else:
            dp[b][a] = min(dp[b-1][a]-aa[b-1], dp[b][a+1]-aa[a])

#print(dp)
print(dp[n][0])

Submission status: Accepted

Solution code:
def kukan(n, 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):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Submission status: Accepted

Solution code:
n=int(input())
v=list(map(int, input().split()))
dp=[[-1] * n for i in range(n)]
def f(a, b):
    if a > b:
        return 0
    elif a == b:
        return v[a]
    elif dp[a][b] == -1:
        c1 = v[a] + min(f(a + 2, b), f(a + 1, b - 1))
        c2 = v[b] + min(f(a, b - 2), f(a + 1, b - 1))
        dp[a][b] = max(c1, c2)
    return dp[a][b]

print(2*f(0, n-1) - sum(v))

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 index in range(N):
    dp[index][index] = A[index]

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]
        dp[i][j] = max(l,r)

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

Submission status: Accepted

Solution code:
def kukan(n, 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):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Submission status: Accepted

Solution code:
def kukan(n, 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]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

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 k in range(1, N + 1):
    for l in range(N - k + 1):
        r = l + k
        if (N - k) % 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])

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

Submission status: Accepted

Solution code:
import sys
# input処理を高速化する
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()))

    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    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()

Submission status: Accepted

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

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

m = n % 2

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
A=tuple(map(int,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
for j in range(1,n+1):
    for i in range(n-j+1):
        DP[j][i]=max(A[i]-DP[j-1][i+1],A[i+j-1]-DP[j-1][i])
print(DP[n][0])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    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]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            # dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))

Submission status: Accepted

Solution code:
def fun(i,j):
	# print(i,j)
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))

for i in range(n-1,-1,-1):
	for j in range(i,n,1):
		if i==j:
			dp[i][j]=arr[i]
		else:
			dp[i][j]=max(arr[i]-dp[i+1][j],arr[j]-dp[i][j-1])
		# print(dp[i])
print(dp[0][n-1])
# print(2*fun(0,n-1)-sum(arr))

Submission status: Accepted

Solution code:
def fun(i,j):
	# print(i,j)
	if i>j or i>=n or j<0:
		return 0
	elif i==j:
		dp[i][j]=arr[i]
		return dp[i][j]
	else:
		if dp[i][j]==0:
			dp[i][j]=max(arr[i]+min(fun(i+1,j-1),fun(i+2,j)),arr[j]+min(fun(i+1,j-1),fun(i,j-2)))
		return dp[i][j]
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*n
arr=list(map(int,input().split()))
print(2*fun(0,n-1)-sum(arr))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(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][n-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

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


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


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*(n+1) for j in range(n+1)]

## dp[j][i]:iは始点、jは列の長さを表す
for i in range(n):
  dp[0][i] = 0

for j in range(1,n+1):
  for i in range(n):
    if i+j <= n:
      dp[j][i] = max(a[i]-dp[j-1][i+1],a[i+j-1]-dp[j-1][i])
print(dp[n][0])

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = list(map(int,input().split(" ")))

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

for l in range(N-1,-1,-1):
    for r in range(l,N):
        turn = ((N - r) + l + 1) % 2

        if turn == 0:
            if r > 0 and l < N-1:
                dp[l][r] = max(a[l] + dp[l+1][r],a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] =  a[l] + dp[l+1][r]
            else:
                dp[l][r] =  a[r] + dp[l][r-1]
        else:
            if r > 0 and l < N-1:
                dp[l][r] = min(-a[l] + dp[l+1][r],-a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] = -a[l] + dp[l+1][r]
            else:
                dp[l][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 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]
for w in range(1, n):
    for l in range(n - w):
        dp[l][l+w] = max(a[l] - dp[l+1][l+w], a[l+w] - dp[l][l+w-1])
print(dp[0][n-1])

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    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 l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * N for _ in range(N+1)]
    dp[1] = A
    for length in range(2, N+1):
        for idx in range(N - length + 1):
            dp[length][idx] = max(A[idx] - dp[length-1][idx+1],
                                  A[idx+length-1] - dp[length-1][idx])
    print(dp[N][0])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for j in range(2, N + 1):
    for i in range(0, N + 1 - j):
        # j is the length of the interval + 1
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i],
                               dp[i][i + j - 1] - a[i + j - 1])

print(dp[0][N])

Submission status: Accepted

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

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

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

print(dp[0][N])

Submission status: Accepted

Solution code:
N=int(raw_input())
A=[int(x) for x in raw_input().split()]
B=[[0 for x in range(N+1)] for y in range(N)]
for i in range(N):
    B[i][i+1]=A[i]
for l in range(1,N):
    for i in range( N-l):
        B[i][i+l+1]=max(A[i]-B[i+1][i+l+1], A[i+l] - B[i][i+l]  )
print B[0][N]
#for ll  in B:
#    print ll

Submission status: Accepted

Solution code:


n = input()
a = map(int, raw_input().split())
oo = sum(a) + 1

dp_max = [[-oo] * n for _ in range(n)]
dp_min = [[oo] * n for _ in range(n)]

for i in range(n):
    dp_max[i][i] = a[i]
    dp_min[i][i] = -a[i]

for i in range(1, n):
    for j in range(n - i):
        k = i + j
        dp_max[j][k] = max(dp_min[j + 1][k] + a[j], dp_min[j][k - 1] + a[k])
        dp_min[j][k] = min(dp_max[j + 1][k] - a[j], dp_max[j][k - 1] - a[k])
print(dp_max[0][n - 1])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/tasks/dp_l
# N,M = map(int, input().split())
N = int(input())
# A = list(map(int, input().split()))
A = tuple(map(int, input().split()))

dp = [ [0]*(N+1) for _ in range(N+1)]
for d in range(1,N+1):
    for l in range(N+1-d):
        r = l+d
        dp[l][r] = \
        max(
            A[l] - dp[l+1][r],
            A[r-1] - dp[l][r-1]
                )
print(dp[0][N])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/tasks/dp_l
# N,M = map(int, input().split())
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 l in range(N+1-d):
        r = l+d
        dp[l][r] = \
        max(
            A[l] - dp[l+1][r],
            A[r-1] - dp[l][r-1]
                )
print(dp[0][N])

Submission status: Accepted

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

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

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

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

print(dp[0][0])

Submission status: Accepted

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

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

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

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

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

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

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



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

print(SCORE[0][N])

Submission status: Accepted

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

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

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

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

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



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

print(SCORE[0][N])

Submission status: Accepted

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

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

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


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

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

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

    return t[0][-1]


print(main())

Submission status: Accepted

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

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

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

print(dp[0][N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
a=[int(i) for i in input().split()]
dp=[[0]*(N+1) for i in range(N+1)]
for d in range(1,N+1):
  for i in range(N+1-d):
    if (N-d)%2==0:
      dp[i][i+d]=max(dp[i+1][i+d]+a[i],dp[i][i+d-1]+a[i+d-1])
    if (N-d)%2==1:
      dp[i][i+d]=min(dp[i+1][i+d],dp[i][i+d-1])
print(2*dp[0][N]-sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
i = 0
j = N-1
def maximize(A,i,j,turn):
	if i==j:
		return A[i]
	if turn==X:
		return min(A[i]+maximize(A,i+1,j,Y),A[j]+maximize(A,i,j-1,Y))
	if turn==Y:
		return max(A[i]+maximize(A,i+1,j,X),A[j]+maximize(A,i,j-1,X))

print(maximize(A,i,j,X))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))


@lru_cache(maxsize=None)
def score(l, r):
    if l == r:
        return A[l]
    return max(A[l]-score(l+1, r), A[r]-score(l, r-1))


print(score(0, N-1))