Problem:
 Score : 100 points    Problem Statement Taro and Jiro will play the following game against each other.  Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N) .
Until a becomes empty, the two players perform the following operation alternately, starting from Taro:   Remove the element at the beginning or the end of a . The player earns x points, where x is the removed element.   Let X and Y be Taro's and Jiro's total score at the end of the game, respectively.
Taro tries to maximize X - Y , while Jiro tries to minimize X - Y .  Assuming that the two players play optimally, find the resulting value of X - Y .      Constraints  All values in input are integers.  1 \leq N \leq 3000  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  \ldots  a_N       Output Print the resulting value of X - Y , assuming that the two players play optimally.        Sample Input 1 4
10 80 90 30      Sample Output 1 10  The game proceeds as follows when the two players play optimally (the element being removed is written bold):   Taro: (10, 80, 90, 30 ) → (10, 80, 90)  Jiro: (10, 80, 90 ) → (10, 80)  Taro: (10, 80 ) → (10)  Jiro: ( 10 ) → ()   Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100 .       Sample Input 2 3
10 100 10      Sample Output 2 -80  The game proceeds, for example, as follows when the two players play optimally:   Taro: ( 10 , 100, 10) → (100, 10)  Jiro: ( 100 , 10) → (10)  Taro: ( 10 ) → ()   Here, X = 10 + 10 = 20 and Y = 100 .       Sample Input 3 1
10      Sample Output 3 10       Sample Input 4 10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1      Sample Output 4 4999999995  The answer may not fit into a 32-bit integer type.       Sample Input 5 6
4 2 9 7 1 5      Sample Output 5 2  The game proceeds, for example, as follows when the two players play optimally:   Taro: (4, 2, 9, 7, 1, 5 ) → (4, 2, 9, 7, 1)  Jiro: ( 4 , 2, 9, 7, 1) → (2, 9, 7, 1)  Taro: (2, 9, 7, 1 ) → (2, 9, 7)  Jiro: (2, 9, 7 ) → (2, 9)  Taro: (2, 9 ) → (2)  Jiro: ( 2 ) → ()   Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13 .

Solution (Python):
import sys
from functools import lru_cache
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    dp = [[-1]*(N+1) for _ in range(N+1)]

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

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

    print(dp[0][N])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')

@lru_cache(maxsize=None)
def f(N, *A):
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][i] = 0
    for l in range(1, N + 1):
        for i in range(N - l + 1):
            j = i + l
            if (N - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
    print(dp[0][N])

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    f(N,*A)

if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N = ni()
a_array = na()

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

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

Solution (Python):
def main():
    n = int(input())
    seq = tuple(map(lambda x: int(x), input().split()))

    points = []
    for i in range(n - 1):
        points.append([0] * n)

    if n == 1:
        print(seq[0])
        return

    for i in range(n - 1):
        points[i][i + 1] = (
            max(seq[i], seq[i + 1]),
            min(seq[i], seq[i + 1])
        )

    for k in range(2, n):
        for i in range(n - k):
            currLeft = seq[i] + points[i + 1][i + k][1]
            currRight = seq[i + k] + points[i][i + k - 1][1]
            nextLeft = points[i + 1][i + k][0]
            nextRight = points[i][i + k - 1][0]

            if currLeft > currRight:
                points[i][i + k] = (currLeft, nextLeft)
            else:
                points[i][i + k] = (currRight, nextRight)

        points.pop()

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

main()

Solution (Python):
def main():
    n = int(input())
    seq = tuple(map(lambda x: int(x), input().split()))

    points = []
    for i in range(n - 1):
        points.append([0] * n)

    if n == 1:
        print(seq[0])
        return

    for i in range(n - 1):
        points[i][i + 1] = (
            max(seq[i], seq[i + 1]),
            min(seq[i], seq[i + 1])
        )

    for k in range(2, n):
        for i in range(n - k):
            currLeft = seq[i] + points[i + 1][i + k][1]
            currRight = seq[i + k] + points[i][i + k - 1][1]
            nextLeft = points[i + 1][i + k][0]
            nextRight = points[i][i + k - 1][0]

            if currLeft > currRight:
                points[i][i + k] = (currLeft, nextLeft)
            else:
                points[i][i + k] = (currRight, nextRight)

        points.pop()

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

main()

Solution (Python):










import sys

def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)


N = iIn()
A = iInLH()

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l in range(1, N+1):
    for i in range(N+1-l):
        j = i + l
        if l % 2 == N % 2:
            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])

ans = dp[0][N]
print(ans)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
dp = [[-1 for i in range(3010)] for j in range(3010)]
for i in range(3010):
    dp[i][i] = 0
for len in range(1, N+1):
    for i in range(N - len + 1):
        j = i + len
        if (N - len) % 2 == 0: 
            
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1]) 

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

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

ans = 0

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

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)

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

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

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

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

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

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal











 



 

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

def pr_list(a):
	print(*a, sep=" ")
def main():
	
	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( 2*dp[0][n-1] - sum(a))
				





		
		


if __name__== "__main__":
	main()

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

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

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

Solution (Python):
N = int(input())
A = 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):
        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])

Solution (Python):
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:
            
            dp[i][x] = max(dp[i+1][x] + A[i], dp[i][x-1] + A[x-1])
        elif (N-k) % 2 == 1:
            
            dp[i][x] = min(dp[i+1][x] - A[i], dp[i][x-1] - A[x-1])
            
print(dp[0][N])

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

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

Solution (Python):
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)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

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

print(func())

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

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

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

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

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

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


solve()

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

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

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[0][n])

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(N)] for _ in range(N)]
    for length in range(1, N + 1):
        for left in range(N - length + 1):
            right = left + length - 1
            val = 0
            if left == right:
                val = A[left]
            else:
                val = max([
                    A[left] - dp[left + 1][right],
                    A[right] - dp[left][right - 1]
                ])
            dp[left][right] = val
    print(dp[0][N - 1])


if __name__ == '__main__':
    main()

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

Solution (Python):

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

Solution (Python):


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

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



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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    
    dp=[[0]*(n+1) for _ in range(n+1)] 
    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])

if __name__=='__main__':
    main()

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):


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

dp = [[0] * (n + 1) for 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])

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

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

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

Solution (Python):

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

Solution (Python):
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])

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

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

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

Solution (Python):
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(dp[0][n-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
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()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
d=[[0]*(N+1) for i in range(N+1)]
for w in range(1,N+1):
    if w%2==N%2:
        for l in range(N+1-w):
            d[l][l+w]=max(d[l][l+w-1]+A[l+w-1],d[l+1][l+w]+A[l])
    else:
        for l in range(N+1-w):
            d[l][l+w]=min(d[l][l+w-1]-A[l+w-1],d[l+1][l+w]-A[l])
print(d[0][N])

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

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

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

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

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