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())
lst = list(map(int, input().split()))

ans = 0

dp = [[0] * (n+1) for _ in range(n+1)] #dp[i]は石の数が残りi個のときに手番プレイヤーが勝利できるか

for i in range(n+1):
    for j in range(n - i+1):
        l = j
        r = j+i
        if l-r== 0:
            dp[l][r] == 0
        elif (n - (l - r-1)) % 2  ==1:
            dp[l][r] =  max(dp[l+1][r] + lst[l], dp[l][r-1] + lst[r-1])
        else:
            dp[l][r] =  min(dp[l+1][r] -  lst[l], dp[l][r-1] -  lst[r-1])
           
ans = dp[0][n]            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

lista = list(map(int,input().split()))

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [[None]*(n+1) for _ in range(n+1)] # a[i:j]に対する解
for i in range(n+1):
    dp[i][i] = 0
for d in range(1,n+1):
    for i in range(n-d+1):
        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])

Submission status: Accepted

Solution code:
N = int(input())
*a, = 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(j-1, -1, -1):
        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, = 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(j-1, -1, -1):
        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, =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=l+length
        if (n-length)%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][-1])

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	for test in range(tests):
		n = inp()
		a = inlt()
		pre =[a[0]]
		for i in range(1,n):
			pre.append(pre[-1] + a[i])
		dp = [[-1*sys.maxsize for j in range(n)] for i in range(n)]
		for i in range(n-1,-1,-1):
			dp[i][i] = a[i]
			for j in range(i+1,n,1):
				dp[i][j] = max( a[i] + (pre[j] - pre[i]) - dp[i+1][j] , a[j] + pre[j-1] - pre[i] + a[i]  - dp[i][j-1])
		# print(dp)
		print( 2*dp[0][n-1] - sum(a))
				





		
		


if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	a = list(map(int, input().split()))
	dp = [0 for i in range(N)]
	for i in range(N-1, -1, -1):
		dp[i] = a[i]
		prev = dp[i]
		for j in range(i+1, N):
			right = a[i] - dp[j]
			left = a[j] - prev
			if right > left:
				dp[j] = right
				prev = right
			else:
				dp[j] = left
				prev = left
	print(dp[-1])

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
 
    dp = [0 for i in range(N)]
 
    for i in range(N-1, -1, -1):
        dp[i] = a[i]
        prev = dp[i]
        for j in range(i+1, N):
            right = a[i] - dp[j]
            left = a[j] - prev
            if right > left:
                dp[j] = right
                prev = right
            else:
                dp[j] = left
                prev = left
    print(dp[-1])
 
 
main()

Submission status: Accepted

Solution code:
def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

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

    if N%2 == 1:
        dp = [A for A in As]
    else:
        dp = [-A for A in As]

    for W in range(2, N+1):
        dp2 = [0] * (N-W+1)
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp2[L] = max2(As[L]+dp[L+1], As[R]+dp[L])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp2[L] = min2(-As[L]+dp[L+1], -As[R]+dp[L])
        dp = dp2

    print(dp[0])


solve()

Submission status: Accepted

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

#半開区間で考える⇒[i,j)での最適解
for w in range(1,N+1):#区間の残り数
    for l in range(N):# 左端
        r = l + w#右端
        if r > N:
            continue
        elif (N-w) % 2 == 0:#太郎
            dp[l][r] = max(dp[l+1][r] + A[l], dp[l][r-1] + A[r-1])
        elif (N-w) % 2 == 1:#次郎
            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()))
A = A
dp = [[0] * (N+1) for _ in range(N+1)]

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

for k in range(1,N+1):#区間の残り数
    for i in range(N):#左端
        x = i+k#右端
        if x > N:
            continue
        elif (N-k) % 2 == 0:#太郎
            #print(i,x)
            dp[i][x] = max(dp[i+1][x] + A[i], dp[i][x-1] + A[x-1])
        elif (N-k) % 2 == 1:#次郎
            #print(i,x)
            dp[i][x] = min(dp[i+1][x] - A[i], dp[i][x-1] - A[x-1])
            
print(dp[0][N])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[float("inf")]*(n+1) for _ in range(n)]
z=0
for l in range(n):
    dp[l][l]=0
for k in range(1,n+1):
    for i in range(n-k+1):
        j=i+k
        if 0<=i<=n-2 and 1<=j<=n:
            if (n-(i+j))%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])
        else:
            dp[i][j]=dp[i][j-1]+a[j-1]
print(dp[0][n])

Submission status: Accepted

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

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

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

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            dp[l][r] = max(A[l]-dp[l+1][r], A[r-1]-dp[l][r-1])
                            
    return dp[0][N]

print(func())

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[float("inf")]*(n+1) for _ in range(n)]
z=0
for l in range(n):
    dp[l][l]=0
for k in range(1,n+1):
    for i in range(n):
        j=i+k
        if 0<=i<=n-2 and 1<=j<=n:
            if (n-(i+j))%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])
        elif 0<=i<=n-2 and 0<=j<=n:
            dp[i][j]=dp[i+1][j]+a[i]
        elif 0<=i<=n-1 and 1<=j<=n:
            dp[i][j]=dp[i][j-1]+a[j-1]
        else:
            z=1

print(dp[0][n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-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 j in range(n):
        if j+i>n:
            continue
        if (n-i)%2==0:
            dp[j][i+j]=max(dp[j+1][i+j]+a[j],dp[j][i+j-1]+a[i+j-1])
        else:
            dp[j][i+j]=min(dp[j+1][i+j]-a[j],dp[j][i+j-1]-a[i+j-1])
# print(dp)
print(dp[0][n])

Submission status: Accepted

Solution code:
def findans(i,j,li):
    if i>=len(li) or j<0:
        return 0
    if i==j:
        dp[i][j]=li[i]
    if i+1==j:
        dp[i][j]=max(li[i],li[j])
    if dp[i][j]!=-1:
        return dp[i][j]
    ans1=li[i]+min(findans(i+2,j,li),findans(i+1,j-1,li))
    ans2=li[j]+min(findans(i,j-2,li),findans(i+1,j-1,li))
    dp[i][j]=max(ans1,ans2)
    return dp[i][j]
n=int(input())
li=[int(k) for k in input().split()]
dp=[[-1 for i in range(n)] for j in range(n)]
x=sum(li)
a=findans(0,n-1,li)
b=x-a
print(a-b)

Submission status: Accepted

Solution code:
#dp[i][j] denotes subarray from i to j left
n=int(input())
l=input().split()
li=[int(i) for i in l]
dp=[[0 for i in range(n)]for i in range(n)]
for i in range(n):
	dp[i][i]=li[i]
for gap in range(1,n):
	for start in range(n-gap):
		end=start+gap
		dp[start][end]=max(li[start]-dp[start+1][end],li[end]-dp[start][end-1])
print(dp[0][n-1])

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j] = X-Y value, between i and j
    OPT[i][j] = max(A[i]-OPT[i+1][j], A[j]-OPT[i][j-1])
    OPT[i][i] = A[i]
    """
    N = read_int()
    A = read_ints()
    OPT = [
        [0]*N for _ in range(N)
    ]
    for i in range(N):
        OPT[i][i] = A[i]
    for length in range(1, N):
        for i in range(N-length):
            OPT[i][i+length] = max(A[i]-OPT[i+1][i+length],
                                   A[i+length]-OPT[i][i+length-1])
    return OPT[0][-1]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

# dp[i][j] stores max value of (x-y) in segment from index i to j

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())
li=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):
        if l==r:
            dp[l][r]=li[l]
        else:
            dp[l][r]=max(li[l]-dp[l+1][r],li[r]-dp[l][r-1])
print(dp[0][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[0]*(n+1) for i in range(n+1)]
for d in range(1, n+1):
  for i in range(n+1-d):
    dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
ans = 2*dp[0][n] - L[n]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = deque(rli())
	tot = sum(A)
	dp = [[A[i] if i == j else 0 for j in range(n)] for i in range(n)]
	for c in range(1, n):
		for r in range(c-1, -1, -1):
			dp[r][c] = max(A[r] - dp[r+1][c], A[c] - dp[r][c-1])
	print(dp[0][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

for l in range(N):
    for i in range(N):
        j = i+l
        
        if j>=N:
            continue
        
        if (N-l-1)%2==0:
            if i==j:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j])
        else:
            if i==j:
                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())
a=list(map(int,input().split()))
ans=[[0 for e in range(N+1)] for f in range(N+1)]
for j in range(1,N+1):
 ans[j][1]=a[j-1]
if N>1:
 for i in  range(2,N+1):
  for j in range(1,N+2-i):
   ans[j][i]=max(a[j-1]-ans[j+1][i-1],a[j+i-2]-ans[j][i-1])
print(ans[1][N])

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
tl = sum(l)
dp=[]
for _ in range(n):
    dp.append([0]*n)
for i in range(n):
    dp[i][i]=l[i]
for i in range(n-1):
    dp[i][i+1]=max(l[i],l[i+1])
for i in range(n-1,-1,-1):
    for j in range(i+2,n):
        ans1=l[i]+min(dp[i+2][j],dp[i+1][j-1])
        ans2=l[j]+min(dp[i+1][j-1],dp[i][j-2])
        dp[i][j]=max(ans1,ans2)
a = dp[0][n-1]
b = tl-a
print(a-b)

Submission status: Accepted

Solution code:
import sys

def f(l,beg,end):
    if beg==end:
        dp[beg][end]=l[beg]
        return l[beg]
    if beg+1==end:
        dp[beg][end] = max(l[beg],l[end]) 
        return max(l[beg],l[end])
    if dp[beg][end]!=-1:
        return dp[beg][end]
    ans1=l[beg]+min(f(l,beg+2,end),f(l,beg+1,end-1))
    ans2=l[end]+min(f(l,beg,end-2),f(l,beg+1,end-1))
    dp[beg][end]=max(ans1,ans2)
    return max(ans1,ans2)

n = int(input())
l = list(map(int, input().split()))
tl = sum(l)
dp=[]
for _ in range(n):
    dp.append([-1]*n)
a = f(l,0,n-1)
b = tl-a
print(a-b)

Submission status: Accepted

Solution code:
import sys
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().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(2,n+1):
    for j in range(n-i+1):
        k=j+i-1 
        dp[j][k]=max(a[k]-dp[j][k-1],a[j]-dp[j+1][k])
print(dp[0][len(a)-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    #区間[i,j)のときのX-Yの最大値
    dp=[[0]*(n+1) for _ in range(n+1)] 
    for length in range(1,n+1): #長さ l=j-i
        for i in range(n-length+1): #区間開始0~n-l
            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])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout


def solve():
    n = int(input())
    A = [int(i) for i in stdin.readline().split()]
    dp = [[i,0] for i in A]
    t = [[0,0] for _ in range(len(A))]
    for i in range(1, len(A)):
        for j in range(i, len(A)):
            l = A[j-i] + dp[j][1]
            r = A[j] + dp[j-1][1]
            if l > r:
                t[j][0] = l
                t[j][1] = dp[j][0]
            else:
                t[j][0] = r
                t[j][1] = dp[j-1][0]
        dp = t
        t = [[0,0] for _ in range(len(A))]
    return dp[-1][0] - dp[-1][1]


print(solve())

Submission status: Accepted

Solution code:
#https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp#%E8%A7%A3%E6%B3%953

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 = a[l] - dp[l + 1][r]
        dpr = a[r - 1] - dp[l][r - 1]
        dp[l][r] = max(dpl, dpr)

print(dp[0][n])

Submission status: Accepted

Solution code:

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

    dp = [[0 for i in range(n+2)]for i in range(n+2)]
    # dp [start][end] is the diffence between X and Y
    # such for range start to end
    for start in range(n, 0, -1):
        for end in range(start, n+1):
            if start == end:
                dp[start][end] = a[start-1]
            else:
                dp[start][end] = max(a[start-1]-dp[start+1]
                                     [end], a[end-1]-dp[start][end-1])
    print(dp[1][n])


if __name__ == "__main__":
    main()

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]:
    for j in range(n + 1):
        if i >= j:
            continue
        dp[i][j] = max(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()))

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

for i in range(n)[::-1]:
    for j in range(n + 1):
        if i >= j:
            continue
        minus = (n - i + j) % 2 * (-2) + 1
        dp[i][j] = max(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())
l=[int(x) for x in input().split()]
dp=[[0 for i in range(n+1)] for j in range(n+1)] 
for i in range(n-1,-1,-1):
	for j in range(0,n,1):
		if i==j:
			dp[i][j]=l[i]
		else:
			dp[i][j]=max(l[i]-dp[i+1][j],l[j]-dp[i][j-1])
		#print(i,j)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    dp = [[None] * (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):
            r = l + width
            if r > n:
                break
            turn = (n - (r - l)) & 1
            if turn & 1 == 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])
resolve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = LI()

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

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

print(dp[0][0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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


main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
# 元の数列から連続する区間[i,j) を抜き出した状態から、
# 最善を尽くした場合のX-Yの最大値
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    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
    # sys.setrecursionlimit(100000)

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

Submission status: Accepted

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

Submission status: Accepted

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

#DP[i][j]=A[i]からA[j-1]まで残っていた時のX-Yの予測値(0<=i<=j<=N,i=jならばDP=0)
DP=[[0]*(N+1) for _ in range(N+1)]

#j-i=1から初めてi=0かつj=Nまで、すなわちj-i=Nまで考える
for len in range(1,N+1):
    for i in range(0,N): #0<=i<Nで考えれば良い、というかi<=N-lenで良い
        j=i+len #正直len=1は例外的、maxもminもないが気にしない
        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

#for index1 in range(N+1):
    #string=''
    #for index2 in range(N+1):
        #string+=str(DP[index1][index2])+' '
    #print(string)

print(DP[0][N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
#i-j番目までが残っているときの利益の最大値
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

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

#dp[i][j]はa[i]からa[j]が残ってる状態から取った時のX-Y
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

#forは状態の配列の長さを増やしつつ回す
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])

Submission status: Accepted

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

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[i][j] := 左からi個、右からj個取った状態での最大(最小)得点
dp = list2d(N+1, N+1, 0)
# 初期化：どちらの手番で使う場所かに合わせて-INFかINFにする
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
# 最初の遷移の開始地点(ゲーム終了の状態)は0に
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)