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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)


def ans(chance, a, start, end):
    if start > end:
        return 0
    temp = -1 if chance else 1
    val1 = a[start]*temp + ans((chance+1) % 2, a, start+1, end)
    val2 = a[end]*temp + ans((chance+1) % 2, a, start, end-1)
    return min(val1, val2) if chance else max(val1, val2)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(ans(0, a, 0, n-1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	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 - l)[::-1]:
			dp[l][r] = max(a[l] - dp[l + 1][r], a[n - 1 - r] - dp[l][r + 1])
	print(dp[0][0])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
def dfs(l,r):
	if l+r==n:return 0
	if dp[l][r]:return dp[l][r]
	dp[l][r]=max(a[l]-dfs(l+1,r),a[n-1-r]-dfs(l,r+1))
	return dp[l][r]
print(dfs(0,0))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

    @lru_cache(None)
    def dfs(l, r):
        # base case
        if l == r:
            return 0

        turn = (n - (r - l)) & 1
        if turn & 1 == 0: # first
            return max(A[l] + dfs(l + 1, r), A[r - 1] + dfs(l, r - 1))
        else: # second
            return min(-A[l] + dfs(l + 1, r), -A[r - 1] + dfs(l, r - 1))

    print(dfs(0, n))
resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
n = int(input())
a = list(map(int,input().split()))
dp = [0]*(n*n)
flag =  [0]*(n*n)
def f(i,j):
  if flag[n*i+j]:
    return dp[n*i+j]
  flag[n*i+j] = 1
  if i == j:
    dp[n*i+j] = a[i]
    return dp[n*i+j]
  else:
    dp[n*i+j] = max(a[i]- f(i+1,j),a[j]-f(i,j-1))
    return dp[n*i+j]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
a = list(map(int,input().split()))
dp = [0]*(n*n)
flag =  [False]*(n*n)
def f(i,j):
  if flag[n*i+j]:
    return dp[n*i+j]
  flag[n*i+j] = True
  if i == j:
    dp[n*i+j] = a[i]
    return dp[n*i+j]
  else:
    dp[n*i+j] = max(a[i]- f(i+1,j),a[j]-f(i,j-1))
    return dp[n*i+j]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for _ in range(n)]for _ in range(n)]
flag =  [[False for _ in range(n)]for _ in range(n)]
def f(i,j):
  if flag[i][j]:
    return dp[i][j]
  flag[i][j] = True
  if i == j:
    dp[i][j] = a[i]
    return dp[i][j]
  else:
    dp[i][j] = max(a[i]- f(i+1,j),a[j]-f(i,j-1))
    return dp[i][j]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

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

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

    for i in range(N-1, -1, -1):
        for j in range(i+1, N+1):
            if i < N-1 and (dp[i][j][0] == 0 or (dp[i][j][0] - dp[i][j][1] < dp[i+1][j][1] + a[i] - dp[i+1][j][0])):
                dp[i][j][0] = dp[i+1][j][1] + a[i]
                dp[i][j][1] = dp[i+1][j][0]
            if j > 0 and (dp[i][j][0] == 0 or (dp[i][j][0] - dp[i][j][1] < dp[i][j-1][1] + a[j-1] - dp[i][j-1][0])):
                dp[i][j][0] = dp[i][j-1][1] + a[j-1]
                dp[i][j][1] = dp[i][j-1][0]
    # print(dp)
    print(dp[0][N][0] - dp[0][N][1])


main()

Submission status: Time Limit Exceeded

Solution code:
N, *A = map(int, open(0).read().split())

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[i * N1 + i] = dpmax[i * N1 + i] = 0
    for i in range(N):
        dpmin[i * N1 + i + 1] = -a[i]
        dpmax[i * N1 + i + 1] = a[i]

    def minimize(a, begin, end):
        x = dpmin[begin * N1 + end]
        if x >= 0:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin * N1 + end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin * N1 + end]
        if x >= 0:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin * N1 + end] = r
        return r

    return maximize(a, 0, N)


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    dpmin = [[None] * (N + 1) for _ in range(N + 1)]
    dpmax = [[None] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dpmin[i][i] = dpmax[i][i] = 0
    for i in range(N):
        dpmin[i][i + 1] = -a[i]
        dpmax[i][i + 1] = a[i]

    def minimize(a, begin, end):
        x = dpmin[begin][end]
        if x is not None:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin][end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin][end]
        if x is not None:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin][end] = r
        return r

    return maximize(a, 0, N)


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(s,e):
    if s>e:
        return 0
    if d[s][e]==-1:
        d[s][e]=max(a[s]-f(s+1,e),a[e]-f(s,e-1))
    return d[s][e]
n=input()
d=[[-1]*n for _ in xrange(n)]
a=map(int,raw_input().split())
print f(0,n-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(s,e,d):
    if s>e:
        return 0
    if (s,e) not in d:
        d[s,e]=max(a[s]-f(s+1,e,d),a[e]-f(s,e-1,d))
    return d[s,e]
n=input()
a=map(int,raw_input().split())
print f(0,n-1,{})

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(s,e,d):
    if s>e:
        return 0
    if (s,e) not in d:
        d[s,e]=max(a[s]-f(s+1,e,d),a[e]-f(s,e-1,d))
    return d[s,e]
n=input()
a=map(int,raw_input().split())
print f(0,n-1,{})

Submission status: Time Limit Exceeded

Solution code:


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

    # dp[i][j] : i ~ j - 1までの数列におけるX - Yのスコア
    # taroのターンの場合、
    #   max(dp[i + 1][j] + iスコア, dp[i][j - 1] + jスコア)
    # jiroのターンの場合
    #   min(dp[i + 1][j] - iスコア, dp[i][j - 1] - jスコア)

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

    # len = 1, 2, 3, ...と求めてゆく
    # len = xのとき、dp[i + 1][j]かdp[i][j - 1]はlen = x - 1のときのスコアなので
    # 計算済み
    for l in range(1, n + 1):
        for i in range(n):
            j = i + l
            if j > n:
                break
            
            # taroのターン, nと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])
            

submit()

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if i == j:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]
print(dp(0, n))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print(2*dp[0][-1]-sa[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
d={}
def k(a):
      return ','.join(map(str,a))
def dp(a):
      ka=k(a)
      if ka in d:
            return [d[ka][0],d[ka][1]]
      if len(a)==1:
            d[ka]=[a[0],[]]
            return a[0],[]
      elif len(a)==2:
            d[ka]=[max(a),[min(a)]]
            return max(a),[min(a)]
      else:
            if a[0]-dp(a[1:])[0]>a[-1]-dp(a[:-1])[0]:
                  d[ka]=[a[0],a[1:]]
                  return a[0],a[1:]
            else:
                  d[ka]=[a[-1],a[:-1]]
                  return a[-1],a[:-1]
x,y=0,0
while a!=[]:
      x_,a=dp(a)
      x+=x_
      if a==[]:
            break
      y_,a=dp(a)
      y+=y_
print(x-y)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n+1)]


def dp(i, j):
    if j <= i:
        DP[i][j] = 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]


print(dp(0, n))

Submission status: Time Limit Exceeded

Solution code:
def deque(array: list, N: int) -> int:
    dp = [[0 for _ in range(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] = array[L]
            else:
                dp[L][R] = max(array[L] - dp[L + 1][R], array[R] - dp[L][R-1])
    #print(dp)
    return dp[0][N-1]


N = int(input())
sums = list(map(int, input().split()))
print(deque(sums, N))

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[-1]*n for i in range(n)]
def memo(i,j):
    if dp[i][j]>=0:
        return dp[i][j]
    if i==j:
        dp[i][j]=a[i]
    else:
        dp[i][j]=max(a[i]-memo(i+1,j),a[j]-memo(i,j-1))
    return dp[i][j]
print(memo(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*n for i in range(n)]
flag=[[0]*n for i in range(n)]
def memo(i,j):
    if flag[i][j]:
        return dp[i][j]
    flag[i][j]=1
    if i==j:
        dp[i][j]=a[i]
    else:
        dp[i][j]=max(a[i]-memo(i+1,j),a[j]-memo(i,j-1))
    return dp[i][j]
print(memo(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
def solve(a):
    dp = [[-1]*len(a) for _ in range(len(a))]
    def _solve(l, r):
        if l > r:
            return 0
        if dp[l][r] == -1:
            dp[l][r] = max(
                a[l] + min(_solve(l+2, r), _solve(l+1, r-1)), 
                a[r] + min(_solve(l, r-2), _solve(l+1, r-1))
            )
        return dp[l][r]
    return 2 * _solve(0, len(a)-1) - sum(a)
    # # print(a)
    # # print()
    # # for row in dp:
    # #     print(row)
    # return 2 * sol - sum(a)

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

Submission status: Time Limit Exceeded

Solution code:
def solve(a):
    def _solve(l, r):
        if l > r:
            return 0
        return max(a[l] + min(_solve(l+2, r), _solve(l+1, r-1)), a[r] + min(_solve(l, r-2), _solve(l+1, r-1)))
    return 2 * _solve(0, len(a)-1) - sum(a)

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

Submission status: Time Limit Exceeded

Solution code:
def solve(a):
    dp = {}
    def _solve(l, r):
        if l > r:
            return 0
        if (l, r) not in dp:
            dp[(l, r)] = max(a[l] + min(_solve(l+2, r), _solve(l+1, r-1)), a[r] + min(_solve(l, r-2), _solve(l+1, r-1)))
        return dp[(l, r)]
    return 2 * _solve(0, len(a)-1) - sum(a)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
INF = 987456325585
arr  = [int(x) for x in input().split()]

# dp[i][j] -> array is left with elements from index i to j, contains max of x-y if player x starts from here

# dp[0][n-1] -> res

dp = []
for i in range(n):
    dp.append([-INF]*n)

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, 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):
        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: Time Limit Exceeded

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

dp=[[-10**12]*(n+1) for i in range(n+1)]
#dp[i][j]:=A[j:j+i+1]
if n%2==0:
  for i in range(n):
    dp[0][i]=-1*A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==1:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
else:
  for i in range(n):
    dp[0][i]=A[i]
  for i in range(1,n+1):
    for j in range(n-i):
      if i%2==0:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]+A[j]
        else:
          dp[i][j]=max(dp[i-1][j]+A[j+i],dp[i-1][j+1]+A[j])
      else:
        if j+i==n:
          dp[i][j]=dp[i-1][j+1]-A[j]
        else:
          dp[i][j]=min(dp[i-1][j]-A[j+i],dp[i-1][j+1]-A[j])
print(dp[n-1][0])

Submission status: Time Limit Exceeded

Solution code:
#EDPC L
import sys
sys.setrecursionlimit(10**5)


def main():

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

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

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

    def rec(l,r):
        if dp[l][r]!=-1:
            return dp[l][r]
        
        if l==r:
            dp[l][r]=a[l]
            return dp[l][r]
        
        dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

        return dp[l][r]


    print(rec(0,N-1))
main()

Submission status: Time Limit Exceeded

Solution code:
#EDPC L
import sys
sys.setrecursionlimit(10**5)

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

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

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

def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

Submission status: Time Limit Exceeded

Solution code:
#EDPC L
import sys
sys.setrecursionlimit(10**8)

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

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

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


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    dp = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = a[i]
    
    for i in range(N-1,-1,-1):
        for j in range(i,N):
            if dp[i][j] != -1:
                continue
            dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])
            
    print(dp[0][-1])
   
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    memo = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        memo[i][i] = a[i]
    
    def point(x,y):
        if memo[x][y] != -1:
            return memo[x][y]
        else:
            ret = max(a[x]-point(x+1,y),a[y]-point(x,y-1))
            memo[x][y] = ret
            return ret
            
    point(0,N-1)
    print(memo[0][N-1])
   
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp_memo = [[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp_memo[i][i] = 0

def dp(i,j):
    if dp_memo[i][j] < float("inf"):
        return dp_memo[i][j]
    elif (j-i)%2 == N%2: # 先手番
        tmp = max(a[i] + dp(i+1, j), a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp
    else: # 後手番
        tmp = min(-a[i] + dp(i+1, j), -a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp

print(dp(0, N))

Submission status: Time Limit Exceeded

Solution code:
def solve(l, r, A, dp):
    #print(l,r)
    if r - l < 2:
        return max(A[l:r + 1])

    x1 = solve(l + 2, r, A, dp)#dp[l + 2][r] if dp[l + 2][r] != -1 else solve(l + 2, r, A, dp)
    x2 = solve(l + 1, r - 1, A, dp)#dp[l + 1][r - 1] if dp[l + 1][r - 1] != -1 else solve(l + 1, r - 1, A, dp)
    x3 = solve(l, r - 2, A, dp)#dp[l][r - 2] if dp[l][r - 2] != -1 else solve(l, r - 2, A, dp)

    #dp[l][r] = max(min(x1, x2) + A[l], min(x2, x3) + A[r])

    return max(min(x1, x2) + A[l], min(x2, x3) + A[r])#dp[l][r]


N = int(input())
A = [int(i) for i in input().split()]
dp = [[-1] * N for i in range(N)]
print(2*solve(0, N-1, A, dp)-sum(A))

Submission status: Time Limit Exceeded

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

dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = float("inf")
    else: dp[l][r] = -float("inf") 
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
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()))
    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: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
#dp[a][b]でa:残っている数列の長さ b:左端
for w in range(1,N+1):
  for l in range(N-w+1):
    r=l+w
    dpl=-dp[l+1][r]+a[l]
    dpr=-dp[l][r-1]+a[r-1]
    dp[l][r]=max(dpl,dpr)
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
dp=[[[] for i in range(3000)] for j in range(3000)]
n=int(input())
A=list(int(i) for i in input().split())
#dp=[[[] for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i<=j:
            if i==j:
                dp[i][j].append(A[i])
                dp[i][j].append(-A[i])
            else:
                dp[i][j].append(max(A[i]+dp[i+1][j][1],A[j]+dp[i][j-1][1]))
                dp[i][j].append(min(-A[i]+dp[i+1][j][0],-A[j]+dp[i][j-1][0]))
print(dp[0][n-1][0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    dp = [[0]*N for _ in range(N)]
    if N%2 == 0:
        for l in range(N-1, -1, -1):
            for r in range(N):
                if l > r:
                    continue
                if l==r==N-1 or l==r==0:
                    dp[l][N-r-1] = -a[l]
                if l+1==N or N-r-1+1==N:
                    continue
                if (r-l+1)%2 == 0:
                    dp[l][N-r-1] = max(dp[l+1][N-r-1]+a[l], dp[l][N-r-1+1]+a[r])
                else:
                    dp[l][N-r-1] = min(dp[l+1][N-r-1]-a[l], dp[l][N-r-1+1]-a[r])
    else:
        for l in range(N-1, -1, -1):
            for r in range(N):
                if l > r:
                    continue
                if l==r==N-1 or l==r==0:
                    dp[l][N-r-1] = a[l]
                if l+1==N or N-r-1+1==N:
                    continue
                if (r-l+1)%2 == 0:
                    dp[l][N-r-1] = min(dp[l+1][N-r-1]-a[l], dp[l][N-r-1+1]-a[r])
                else:
                    dp[l][N-r-1] = max(dp[l+1][N-r-1]+a[l], dp[l][N-r-1+1]+a[r])
    print(dp[0][0])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
input = sys.stdin.readline
MOD = 10**9 +7
INF = 10**9

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

Submission status: Time Limit Exceeded

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

import random
#N = 20
#A = [random.randint(1, 10**9) for _ in range(N)]


@lru_cache(maxsize=None)
def f(l, r):
  if l > r:
    return 0
  
  n = r - l
  if (N - n) % 2 == 0:
    s = -1
  else:
    s = 1
    
  lv = f(l+1, r) + s*A[l]
  rv = f(l, r-1) + s*A[r]
  
  if s*lv > s*rv:
    return lv
  else:
    return rv
    
   
print(f(0, N-1))