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:
from collections import deque

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

def calc(qLeft, qRight):
    st = deque([(False, qLeft, qRight, True)])
    memo = dict()

    while st:
        canCalc, left, right, isFirst = st.pop()

        if (left, right, isFirst) in memo:
            continue

        if left == right:
            if isFirst:
                memo[(left, right, isFirst)] = A[left]
            else:
                memo[(left, right, isFirst)] = -A[left]
            continue

        if canCalc:
            if isFirst:
                ret = max(
                    memo[(left + 1, right, not isFirst)] + A[left],
                    memo[(left, right - 1, not isFirst)] + A[right]
                )
            else:
                ret = min(
                    memo[(left + 1, right, not isFirst)] - A[left],
                    memo[(left, right - 1, not isFirst)] - A[right]
                )
            memo[(left, right, isFirst)] = ret
        else:
            st.append((True, left, right, isFirst))

            if not (left + 1, right, not isFirst) in memo:
                st.append((False, left + 1, right, not isFirst))
            if not (left, right - 1, not isFirst) in memo:
                st.append((False, left, right - 1, not isFirst))

    return memo[(left, right, True)]

ans = calc(0, N - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n)[::-1]:
    for j in range(i,n):
        if (n+i-j-1)%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: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(x) for x in input().split()]

dp = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l * n + r] is None:
        memo[l * n + r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l * n + r]


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

memo = [None] * pow(n, 2)
for i, aa in enumerate(a):
    memo[n * i + i] = aa

print(func(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l][r] is None:
        memo[l][r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l][r]


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

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

print(func(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人

    # if l == r:
    #     return a[l]
    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]
for i, aa in enumerate(a):
    memo[i][i] = aa

print(func(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    if l == r:
        return a[l]

    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro

    if l == r:
        return a[l] * (-1 if taro_turn is None else 1)

    if memo[l][r] is not None:
        return memo[l][r]

    if taro_turn is None:
        # jiro_turn
        res = min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        res = max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])

    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1, True))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro
    if l > r:
        return 0

    if taro_turn is None:
        # jiro_turn
        return min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        return max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])


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

print(func(0, n - 1, True))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache

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

@lru_cache(maxsize=None)
def seach(left, right, turn):
    if right - left == 1:
        if turn == 0:
            return A[left]
        else:
            return -A[left]

    if turn == 0:  # 最大化
        return max(seach(left + 1, right, 1) + A[left], seach(left, right - 1, 1) + A[right - 1])
    else:
        return min(seach(left + 1, right, 0) - A[left], seach(left, right - 1, 0) - A[right - 1])

ans = seach(0, N, 0)
print(ans)

Submission status: Time Limit Exceeded

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

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

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

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

def f(left, right) :
    if flag[left][right] :
        return dp[left][right]
    elif left == right :
        flag[left][right] = 1
        dp[left][right] = A[left]
        return dp[left][right]
    else :
        flag[left][right] = 1
        dp[left][right] = max(A[left] - f(left+1, right), A[right] - f(left, right-1))
        return dp[left][right]

ans = f(0,N-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
for i in range(N-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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools

N = int(input())
a = list(map(int, input().split()))
@functools.lru_cache(maxsize=None)
def rec(l, r):
    if r < l:
        return 0
    return max(a[l]-rec(l+1, r), a[r]-rec(l, r-1))
print(rec(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
l = [int(j) for j in raw_input().split()]
dp = dict()
for i in range(n):
    dp[i,i] = l[i]
for i in range(n-1)[::-1]:
    for j in range(i+1,n):
        if (i,j) not in dp:
            if i>j:
                dp[i,j]=0
            elif j-1>=0:
                # print(i,j)
                dp[i,j]=max(l[i] - dp[i+1,j], l[j] - dp[i, j-1])
            else:
                dp[i,j] = l[i] - dp[i+1,j]
print(dp[0,n-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(j) for j in input().split()]
dp = dict()
for i in range(n):
    dp[i,i] = l[i]
for i in range(n-1)[::-1]:
    for j in range(i+1,n):
        if (i,j) not in dp:
            if i>j:
                dp[i,j]=0
            elif j-1>=0:
                # print(i,j)
                dp[i,j]=max(l[i] - dp[i+1,j], l[j] - dp[i, j-1])
            else:
                dp[i,j] = l[i] - dp[i+1,j]
print(dp[0,n-1])

Submission status: Time Limit Exceeded

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

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

dp = [[[-1]*2 for i in range(n+1)] for i in range(n+1)]

def solve(s, e, f):
    p = -1 if f==1 else 1
    if (s==e):
        return p*a[s]

    if (dp[s][e][f]!=-1):
        return dp[s][e][f]
    z = max if f==0 else min
    ans = z(p*a[s]+solve(s+1, e, 1-f), p*a[e]+solve(s, e-1, 1-f))
    dp[s][e][f]=ans
    return dp[s][e][f]


print(solve(0, n-1, 0))

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 k in range(1,n+1):
    for i in range(n-k+1):
        j=i+k
        dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1])if(n-k)%2else max(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1])
print(dp[0][n])

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置] = この局面からの結果
memo = [[None] * (N+1) for i in range(N+1)]

def dfs(turn, l, r):
    # 既に見た局面ならメモの内容を返す
    if memo[l][r] is not None:
        return memo[l][r]
    # 全部取り切ったので終了
    if l > r:
        return 0
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(1, l+1, r) + aN[l])
        mx = max(mx, dfs(1, l, r-1) + aN[r])
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(0, l+1, r) - aN[l])
        mn = min(mn, dfs(0, l, r-1) - aN[r])
        memo[l][r] = mn
        return mn

print(dfs(0, 0, N-1))

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(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(n-j):dp[i][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    recursive_call(dp, a, len(a), 0, n - 1)
    return dp[0][n - 1]


def recursive_call(dp, a, n, l, r):
    if dp[l][r] is not None:
        return dp[l][r]
    if l == r:
        dp[l][r] = a[l]
        return dp[l][r]
    dp[l][r] = max(a[l] - recursive_call(dp, a, n, l + 1, r), a[r] - recursive_call(dp, a, n, l, r - 1))
    return dp[l][r]


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    recursive_call(dp, a, 0, n - 1)
    return dp[0][n - 1]


def recursive_call(dp, a, l, r):
    n = len(dp)
    if dp[l][r] is not None:
        return dp[l][r]
    if l == r:
        dp[l][r] = a[l]
        return dp[l][r]
    dp[l][r] = max(a[l] - recursive_call(dp, a, l + 1, r), a[r] - recursive_call(dp, a, l, r - 1))
    return dp[l][r]


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    solve()

Submission status: Time Limit Exceeded

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

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

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

X = dp[0][N-1]
S = sum(a)
Y = S-X
print X-Y

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if n%2 ==0:
        dp[i][i]=-s[i]
        turn =0
    else:
        dp[i][i]=s[i]
        turn = 1
def findMax(i,j):
    dp[i][j] = max(dp[i+1][j]+s[i],dp[i][j-1]+s[j])
def findMin(i,j):
    dp[i][j]= min(dp[i+1][j]-s[i],dp[i][j-1]-s[j])
for length in range(2,n+1):
    for j in range(n-length+1):
        if not turn:
            findMax(j,j+length-1)
        else:
            findMin(j,j+length-1)
    turn^=1

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = {}
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.get((i + 1, j), 0),
                         a[j] - dp.get((i, j - 1), 0))

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = {}

def dp(i, j, turn = 1):
    if i == j: return 0
    if (i,j) in MEMO: return MEMO[(i,j)]

    xy1 = dp(i, j-1, -turn) + turn*A[j-1]
    xy2 = dp(i+1, j, -turn) + turn*A[i]
    res = xy1 if turn*xy1 > turn*xy2 else xy2
    MEMO[(i,j)] = res
    return res

print(dp(0, len(A), 1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MAX_INT = 100

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

dp = np.array([[100]*(N) for i in range(N+1)])

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

for i in range(N):
  if hand == 0:
    dp[i][i] = -a[i]
  else:
    dp[i][i] = a[i]
  
for i in range(1,N+1):
  for j in range(N+1):
    if i+j < N:
      if (hand+i)%2 == 1: # 先手
        dp[j][i+j] = max(dp[j][i+j-1]+a[i+j],dp[j+1][i+j]+a[j])
      else:
        dp[j][i+j] = min(dp[j][i+j-1]-a[i+j],dp[j+1][i+j]-a[j])
    else:
      break  
print(dp[0][-1])

Submission status: Time Limit Exceeded

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

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
aa = inpl()
dp = [[INF]*(N+1) for _ in range(N+1)]

def calc(l,r,first):
    global dp
    if dp[l][r] != INF:
        return dp[l][r]
    if first:
        if l == r:
            return aa[l]
        tmp = max(calc(l,r-1,False)+aa[r],calc(l+1,r,False)+aa[l])
    else:
        if l == r:
            return -aa[l]
        tmp = min(calc(l,r-1,True)-aa[r],calc(l+1,r,True)-aa[l])
    dp[l][r] = tmp
    return tmp

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
aa = inpl()
dp = [[INF]*(N+1) for _ in range(N+1)]

def calc(l,r,first):
    if dp[l][r] != INF:
        return dp[l][r]
    if first:
        if l == r:
            return aa[l]
        return max(calc(l,r-1,False)+aa[r],calc(l+1,r,False)+aa[l])
    else:
        if l == r:
            return -aa[l]
        return min(calc(l,r-1,True)-aa[r],calc(l+1,r,True)-aa[l])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
a = list(map(int,input().split()))

cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]

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

def cal(i,j):
    if dp[i][j] == -1:
        dp[i][j] = cum[j]-cum[i-1]-min(cal(i+1,j),cal(i,j-1))
    return dp[i][j]

print(2*cal(0,N-1)-cum[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def calcdp(p, i, j):
    # すでにテーブルが埋まっていればその値を返す
    if dp[p][i][j] is not None:
        return dp[p][i][j]
    
    # リストに１個しか数字がなければ、それを取るしかない
    if i == j - 1:
        if p:
            dp[p][i][j] = A[i]
        else:
            dp[p][i][j] = -A[i]
        return dp[p][i][j]
    else:
        # 先手の場合
        if p:
            dp[p][i][j] = max(calcdp(not p, i + 1, j) + A[i], calcdp(not p, i, j-1) + A[j-1])
        #　後手の場合
        else:
            dp[p][i][j] = min(calcdp(not p, i + 1, j) - A[i], calcdp(not p, i, j-1) - A[j-1])
        return dp[p][i][j]

    
N = int(input())
A = [int(x) for x in input().split()]

dp = [[[None] * (N+1) for _ in range(N)] for __ in range(2)]

print(calcdp(True, 0, N))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = 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] + arr[i], dp[i][j-1] + arr[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - arr[i], dp[i][j-1] - arr[j-1])


print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    import sys
    #raw = ["4", "10 80 90 30"]
    raw = [sys.stdin.readline(), sys.stdin.readline()]
    N = int(raw[0])
    xs = list(map(int, raw[1].split()))
    M = N + 1
    memo = [[0] * M for _ in range(M)]
    flag = [[False] * M for _ in range(M)]
    # Initialize
    for i in range(N):
        memo[i][i] = 0

    for ll in range(1, N+1):
        for i in range(N - ll + 1):
            j = i + ll
            if (N - ll) % 2 == 0: # 先手
                memo[i][j] = max(memo[i+1][j] + xs[i],
                                 memo[i][j-1] + xs[j-1])
            else: # 後手
                memo[i][j] = min(memo[i+1][j] - xs[i],
                                 memo[i][j-1] - xs[j-1])

    print(memo[0][N])
    #for i in range(M):
    #    print(str("{:4}" * M).format(*memo[i]))
    #pass

main()

Submission status: Time Limit Exceeded

Solution code:
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 l in range(1, n):
    for s in range(n - l):
        dp[s][s + l] = max(a[s] - dp[s + 1][s + l], a[s + l] - dp[s][s + l - 1])
print(dp[0][n - 1])

Submission status: Time Limit Exceeded

Solution code:
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp[0][n - 1]


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

Submission status: Time Limit Exceeded

Solution code:
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):
        L=a[i]-dp[i+1][j]
        R=a[j]-dp[i][j-1]
        dp[i][j]=L if L>R else R
print(dp[0][n-1])

Submission status: Time Limit Exceeded

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

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 d in range(1,n+1):
    for i in range(n-d+1):
        j = i + d
        if (n - i - j) % 2:
            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])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def xy(a, x, y, i):
    if i == n - 2:
        if i % 2:
            return x - y - max(a) + min(a)
        else:
            return x - y + max(a) - min(a)
    t = tuple(a + [x, y])
    if t in memo:
        return memo[t]
    if i % 2:
        L = xy(a[1:], x, y + a[0], i + 1)
        R = xy(a[:-1], x, y + a[-1], i + 1)
        re = min(L, R)
        memo[t] = re
        return re
    else:
        L = xy(a[1:], x + a[0], y, i + 1)
        R = xy(a[:-1], x + a[-1], y, i + 1)
        re = max(L, R)
        memo[t] = re
        return re


memo = {}
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(a[0])
    exit()
print(xy(a, 0, 0, 0))

Submission status: Time Limit Exceeded

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置] = この局面からの結果
memo = [[None] * (N+1) for i in range(N+1)]

def dfs(turn, l, r):
    # 既に見た局面ならメモの内容を返す
    if memo[l][r] is not None:
        return memo[l][r]
    # 全部取り切ったので終了
    if l > r:
        return 0
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(1, l+1, r) + aN[l])
        mx = max(mx, dfs(1, l, r-1) + aN[r])
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(0, l+1, r) - aN[l])
        mn = min(mn, dfs(0, l, r-1) - aN[r])
        memo[l][r] = mn
        return mn

print(dfs(0, 0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)
def max(a,b):
    if a >= b:
        return a
    return b
def min(a,b):
    if a <= b:
        return a
    return b

def main():

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

    dp = [[-1]*(n+1) for i in range(n)]
    def rec(i=0, j=n):
        if i == j:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        # 太郎
        if (n - (j-i))%2==0:
            dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
        else:
            dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
        return dp[i][j]
    print(rec())

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)
def max(a,b):
    if a >= b:
        return a
    return b
def min(a,b):
    if a <= b:
        return a
    return b

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

dp = [[-1]*(n+1) for i in range(n)]

def rec(i=0, j=n):
    if i == j:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    # 太郎
    if (n - (j-i))%2==0:
        dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
    else:
        dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
    return dp[i][j]
print(rec())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
a = list(map(int, input().split()))

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

def rec(i=0, j=n):
    if i == j:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    # 太郎
    if (n - (j-i))%2==0:
        dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
    else:
        dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
    return dp[i][j]
print(rec())

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    if a >= b:
        return a
    return b

def chmin(a, b):
    if a <= b:
        return a
    return b

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

    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    dp = [[0] * (N+2)  for _ in range(N+2)]
    dp[N+1][N+1] = 4999999995

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

arr = list(map(int,input().split()))
dp = [ [0 for i in range(n)] for j in range(n)]

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

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