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

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        dp[i][j] = a[i]
        return dp[i][j]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))

Submission status: Time Limit Exceeded

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

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        return a[i]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [0] * n ** 2

    for i in range(n):
        dp[i * n + i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[(i + 1) * n + j]
            R = a[j] - dp[i * n + j - 1]
            if L > R:
                dp[i * n + j] = L
            else:
                dp[i * n + j] = R
    return dp[n - 1]


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [0] * n ** 2

    def f(i, j):
        return i * n + j

    for i in range(n):
        dp[f(i, i)] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[f(i + 1, j)]
            R = a[j] - dp[f(i, j - 1)]
            if L > R:
                dp[f(i, j)] = L
            else:
                dp[f(i, j)] = R
    return dp[f(0, n - 1)]


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    N, *a = map(int, read().split())
    a = tuple(a)
    INF = float('inf')
    memo = [[INF] * N for _ in range(N)]

    def f(i, j):
        if memo[i][j] != INF:
            return memo[i][j]
        n = j - i + 1
        n %= 2
        if i == j:
            if n == r:
                s = a[i]
            else:
                s = -a[i]
            memo[i][j] = s
            return s
        if n == r:
            s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
        else:
            s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
        memo[i][j] = s
        return s

    r = N % 2
    f(0, N - 1)
    return memo[0][N - 1]


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    N, *a = map(int, read().split())
    a = tuple(a)
    INF = float('inf')
    memo = [[INF] * N for _ in range(N)]

    def f(i, j):
        if memo[i][j] != INF:
            return memo[i][j]
        n = j - i + 1
        if i == j:
            if n % 2 == r:
                s = a[i]
            else:
                s = -a[i]
            memo[i][j] = s
            return s
        if n % 2 == r:
            s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
        else:
            s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
        memo[i][j] = s
        return s

    r = N % 2
    f(0, N - 1)
    return memo[0][N - 1]


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    N, *a = map(int, read().split())
    a = tuple(a)
    memo = [[0] * N for _ in range(N)]

    def f(i, j):
        n = j - i + 1
        if i == j:
            if n % 2 == r:
                s = a[i]
            else:
                s = -a[i]
            memo[i][j] = s
            return s
        if n % 2 == r:
            s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
        else:
            s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
        memo[i][j] = s
        return s

    r = N % 2
    f(0, N - 1)
    return memo[0][N - 1]


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)

N, *a = map(int, read().split())

memo = [[0] * N for _ in range(N)]
r = N % 2


def f(i, j):
    n = j - i + 1
    if i == j:
        if n % 2 == r:
            s = a[i]
            memo[i][j] = s
            return s
        else:
            s = -a[i]
            memo[i][j] = s
            return s
    if n % 2 == r:
        s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
    else:
        s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
    memo[i][j] = s
    return s


f(0, N - 1)
print(memo[0][N - 1])

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 for _ in range(N)]

for l in range(N):
    for i in range(N-l):
        if l == 0:
            dp[i][i] = a[i]
        else:
            j = i + l
            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
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]
flag = [[False] * N for _ in range(N)]

def calc(i, j):
    if flag[i][j]:
        return dp[i][j]
    flag[i][j] = True
    if i == j:
        dp[i][j] = a[i]
    else:
        dp[i][j] = max(a[i] - calc(i+1, j), a[j] - calc(i, j-1))
    return dp[i][j]

print(calc(0, N-1))

Submission status: Time Limit Exceeded

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

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

def calc(i, j):
    if dp[i][j] != INF:
        return dp[i][j]
    if i == j:
        dp[i][j] = a[i]
    else:
        dp[i][j] = max(a[i] - calc(i+1, j), a[j] - calc(i, j-1))
    return dp[i][j]

print(calc(0, N-1))

Submission status: Time Limit Exceeded

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

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

INF = 10**18

# dp0 = [[INF] * N for _ in range(N)]
# dp1 = [[INF] * N for _ in range(N)]
dp = [[INF] * N for _ in range(N)]

def calc(i, j, t):
    if dp[i][j] != INF:
        return dp[i][j]
    if t == 0:
        if i == j:
            dp[i][j] = a[i]
        else:
            dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
    else:
        if i == j:
            dp[i][j] = -a[i]
        else:
            dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
    return dp[i][j]
    # if t == 0:
    #     if dp0[i][j] == INF:
    #         if i == j:
    #             dp0[i][j] = a[i]
    #         else:
    #             dp0[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
    #     return dp0[i][j]
    # else:
    #     if dp1[i][j] == INF:
    #         if i == j:
    #             dp1[i][j] = -a[i]
    #         else:
    #             dp1[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
    #     return dp1[i][j]

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

Submission status: Time Limit Exceeded

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

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

INF = 10**18

dp0 = [[INF] * N for _ in range(N)]
dp1 = [[INF] * N for _ in range(N)]

def calc(i, j, t):
    if t == 0:
        if dp0[i][j] == INF:
            if i == j:
                dp0[i][j] = a[i]
            else:
                dp0[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
        return dp0[i][j]
    else:
        if dp1[i][j] == INF:
            if i == j:
                dp1[i][j] = -a[i]
            else:
                dp1[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
        return dp1[i][j]

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

Submission status: Time Limit Exceeded

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

dp = [[[None] * 2 for _ in range(n + 1)] for _ in range(n + 1)]
# def dfs(l=0, r=n, taro=True):
#     if r - l <= 0:
#         return 0
#
#     if dp[l][r][taro] is not None:
#         return dp[l][r][taro]
#
#     if taro:
#         R = max(
#             dfs(l + 1, r, not taro) + a[l],
#             dfs(l, r - 1, not taro) + a[r - 1],
#         )
#     else:
#         R = min(
#             dfs(l + 1, r, not taro) - a[l],
#             dfs(l, r - 1, not taro) - a[r - 1],
#         )
#     dp[l][r][taro] = R
#     return R
#
# print(dfs())

for l in reversed(range(n + 1)):
    for r in range(n + 1):
        for taro in range(2):
            if r - l <= 0:
                dp[l][r][taro] = 0
                continue
            if taro:
                R = max(
                    dp[l + 1][r][not taro] + a[l],
                    dp[l][r - 1][not taro] + a[r - 1],
                )
            else:
                R = min(
                    dp[l + 1][r][not taro] - a[l],
                    dp[l][r - 1][not taro] - a[r - 1],
                )
            dp[l][r][taro] = R
print(dp[0][n][True])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
dp = [[0] * (N+1) for _ in range(N+1)]
for n in range(1, N+1):
    for i in range(N-n+1):
        j = i + n
        if (N - n) % 2 == 0: # first player
            dp[i][j] = max(dp[i+1][j] + A[i], dp[i][j-1] + A[j-1])
        else: # second player
            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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_l
L - Deque / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
太郎君と次郎君が次のゲームで勝負します。
最初に、数列 a=(a1,a2,…,aN) が与えられます。 
a が空になるまで、二人は次の操作を交互に行います。 
先手は太郎君です。a の先頭要素または末尾要素を取り除く。 
取り除いた要素を x とすると、操作を行った人は x 点を得る。
ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 
太郎君は X−Y を最大化しようとし、次郎君は X−Y を最小化しようとします。

二人が最適に行動すると仮定したとき、X−Y を求めてください。

解説:
ただの区間DP
しかし、Pythonはカスなので工夫が必要
知見
    ====================================================================
    |dp[i][j]に-dp[i][j-1] or -dp[i+1][j]の加算結果を与えれば             |
    |    右辺の式はすべて符号反転するので－側の最小を目指すというのと         |
    |        ＋の最大を目指すというのを満たすのでその区間における            |
    |           プレイヤーの最善スコアが出る                               |
    ====================================================================|

"""

#solve
def solve():
    n = II()
    a = LI()
    dp = defaultdict(int)
    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)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LI()
    c = defaultdict(int)
    dp = defaultdict(int)
    for i in range(n+1):
        c[(i, i, 0)] = 1
        c[(i, i, 1)] = 1
    def f(l, r, t):
        if c[(l, r, t)]:
            return dp[(l, r, t)]
        c[(l, r, t)] = True
        if t:
            tmp = max(f(l + 1, r, t ^ 1) + a[l], f(l, r - 1, t ^ 1) + a[r - 1])
        else:
            tmp = min(f(l + 1, r, t ^ 1) - a[l], f(l, r - 1, t ^ 1) - a[r - 1])
        dp[(l, r, t)] = tmp
        return tmp
    print(f(0, n, 1))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(9000000)

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

N = int(input())
*a, = map(int, input().split())
print(f(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(9000000)

@lru_cache()
def f(l, r):
    if l==r: return a[r]
    return max(a[l]-f(l+1, r),  a[r]-f(l, r-1))

N = int(input())
*a, = map(int, input().split())
print(f(0, N-1))

Submission status: Time Limit Exceeded

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

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] #X - Yの最大値
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] #X - Yの最小値

if N % 2 == 0: #偶数-->最後の一個はY
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        # print (dp2[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])



else: #奇数-->最後の一個はX
    for i in range(N):
        dp1[i][i + 1] = A[i]
        # print (dp1[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])

Submission status: Time Limit Exceeded

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

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

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

dp=[[0]*(N+1) for _ in range(N+1)]#[l,r)の範囲が残っているときに取れる最大値

def rep(l,r):
    if l==r:
        return 0
    if dp[l][r]!=0:
        return dp[l][r]
    else:
        x=a[l]+(S[r]-S[l+1] - rep(l+1,r))
        y=a[r-1]+(S[r-1]-S[l] - rep(l,r-1))
        dp[l][r]=max(x,y)
        return dp[l][r]
    
    
rep(0,N)
print(2*dp[0][N] - S[-1] )

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[None]*n for _ in range(n)]
for d in range(n):
  for l in range(n-d):
    r = l + d
    if d:
      dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])
    else:
      dp[l][r] = a[l]
print(dp[0][n-1])

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
d = [None]*n**2
def judge(l,r):
  if l >= r: return a[l]
  v = l + r*n
  if d[v] is not None: return d[v] 
  d[v] = max(a[l] - judge(l+1,r), a[r] - judge(l,r-1))
  return d[v]

print(judge(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6 + 2)

n = int(input())
a = list(map(int, input().split()))
d = [None]*3001**2
def judge(l,r):
  if l >= r:
    return a[l]
  v = l + r*3001
  if d[v] is not None: return d[v]
  res1 = a[l] - judge(l+1,r)
  res2 = a[r] - judge(l,r-1)
  if res1 < res2: res1, res2 = res2, res1
  d[v] = res1
  return res1

print(judge(0,n-1))

Submission status: Time Limit Exceeded

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

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if memo[l][r] != -1:
            return memo[l][r]
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )

        memo[l][r] = ret
        return ret

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

    ret = calc()

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )
        return ret

    ret = calc()

    print(ret)


if __name__ == '__main__':
    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 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()))

#check who plays last
currentTaro = ((N%2)==1)

#initilise best-scores list for last player with one element
bestScores = [(el if currentTaro else -el) for el in a]
bestScores = [(el,el) for el in bestScores]

for i in range(1,N):
	#alternate player
	currentTaro = not currentTaro
    
	newBestScores=[(None,None)]*N
    #get best score if number removed from left    
	for j in range(i,N):
		leftScoresAfterRemoval=(bestScores[j-1][0],bestScores[j-i][1])
		bestLeftScore= min(leftScoresAfterRemoval)+a[j] if currentTaro else max(leftScoresAfterRemoval)-a[j]
		newBestScores[j]=(bestLeftScore,None)
     
	#get best score if number removed from right
	for j in range(0,N-i):	
		rightScoresAfterRemoval=(bestScores[j+1][1],bestScores[j+i][0])
		bestRightScore= min(rightScoresAfterRemoval)+a[j] if currentTaro else max(rightScoresAfterRemoval)-a[j]
		newBestScores[j]=(newBestScores[j][0],bestRightScore)
        
	bestScores=newBestScores

#return best score 
result = max(bestScores[0][1],bestScores[-1][0])
print(result)

Submission status: Time Limit Exceeded

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

#check who plays last
currentTaro = ((N%2)==1)

#initilise best-scores list for last player with one element
bestScores = [(el if currentTaro else -el) for el in a]
bestScores = [(el,el) for el in bestScores]

for i in range(1,N):
	#alternate player
	currentTaro = not currentTaro
    
	newBestScores=[(None,None)]*N
    #get best score if number removed from left    
	for j in range(i,N):
		leftScoresAfterRemoval=(bestScores[j-1][0],bestScores[j-i][1])
		bestLeftScore= min(leftScoresAfterRemoval)+a[j] if currentTaro else max(leftScoresAfterRemoval)-a[j]
		newBestScores[j]=(bestLeftScore,None)
        
	#get best score if number removed from right
	for j in range(0,N-i):	
		rightScoresAfterRemoval=(bestScores[j+1][1],bestScores[j+i][0])
		bestRightScore= min(rightScoresAfterRemoval)+a[j] if currentTaro else max(rightScoresAfterRemoval)-a[j]
		newBestScores[j]=(newBestScores[j][0],bestRightScore)
        
	bestScores=newBestScores

#return best score 
result = max(bestScores[0][1],bestScores[-1][0])
print(result)

Submission status: Time Limit Exceeded

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

#check who plays last
currentTaro = ((N%2)==1)

#initilise best-scores list for last player with one element
bestScores = [(el if currentTaro else -el) for el in a]
bestScores = [(el,el) for el in bestScores]

for i in range(1,N):
	#alternate player
	currentTaro = not currentTaro
    
	newBestScores=[]
	for j in range(N):
		#get best score if number removed from left
		bestLeftScore=None
		if j>=i:
			leftScoresAfterRemoval=(bestScores[j-1][0],bestScores[j-i][1])
			bestLeftScore= min(leftScoresAfterRemoval)+a[j] if currentTaro else max(leftScoresAfterRemoval)-a[j]

		#get best score if number removed from right
		bestRightScore=None
		if j<=N-1-i:
			rightScoresAfterRemoval=(bestScores[j+1][1],bestScores[j+i][0])
			bestRightScore= min(rightScoresAfterRemoval)+a[j] if currentTaro else max(rightScoresAfterRemoval)-a[j]

		#add to newBestScores
		newBestScores.append((bestLeftScore,bestRightScore))

	bestScores=newBestScores

#return best score 
result = max(bestScores[0][1],bestScores[-1][0])
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 30 10:20:58 2020

@author: matsui
"""

import numpy as np


def strategy(A):
    ans=0
    if len(A)>=4:
        if A[0]-max(A[1],A[-1]) < A[-1]-max(A[0],A[-2]):
            ans=-1
    if len(A)==3 or len(A)==2:
        if A[0]<A[-1]:
            ans=-1
    return ans

N=int(input())
a=input().split()
a=[int(i) for i in a]

dp=np.zeros([N,N])
for i in range(N):
    dp[i][i]=a[i]

for i in range(N-1):
    dp[i][i+1]=abs(a[i]-a[i+1])
    
for j in range(2,N):
    for i in range(N-j):
        m=a[i]-dp[i+1][i+j]
        if m<a[i+j]-dp[i][i+j-1]: m=a[i+j]-dp[i][i+j-1]
        
        dp[i][i+j]=m
          
#print(dp)
print(int(dp[0][N-1]))

'''
X,Y=0,0

for i in range(N):
    ans=strategy(a)
    if i%2==0:
        X+=a[ans]
    else:
        Y+=a[ans]
    a.remove(a[ans])
    
print(X-Y)
'''

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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


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

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] = max(dp[i+1][j] + lst_a[i], dp[i][j-1] + lst_a[j-1])
		else :
			dp[i][j] = min(-lst_a[i] + dp[i + 1][j], -lst_a[j - 1]+dp[i][j - 1])


print(dp[0][N])

Submission status: Time Limit Exceeded

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

N = int(input())
*a, = 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:
            # first
            dp[i][j] = max([dp[i+1][j]+a[i], dp[i][j-1]+a[j-1]])
        else:
            # second
            dp[i][j] = min([dp[i+1][j]-a[i], dp[i][j-1]-a[j-1]])

print(dp[0][N])
'''


def solve(l, r):
    if l >= r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    t = N-(r-l)
    if t % 2 == 0:
        dp[l][r] = max([solve(l+1, r)+a[l], solve(l, r-1)+a[r-1]])
    else:
        dp[l][r] = min([solve(l+1, r)-a[l], solve(l, r-1)-a[r-1]])
    return dp[l][r]


print(solve(0, N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

N = int(raw_input())
A = list(map(int, raw_input().split()))
optimal_score_cache = {}

def get_optimal_score(i, j):
    if i > j or i >= N or j < 0:
        return 0
    if i == j:
        return A[i]
    if (i, j) in optimal_score_cache:
        return optimal_score_cache[i, j]

    score = max(
        A[i] + min(get_optimal_score(i+2, j), get_optimal_score(i+1, j-1)),
        A[j] + min(get_optimal_score(i+1, j-1), get_optimal_score(i, j-2)))

    optimal_score_cache[i, j] = score

    return score

print 2*get_optimal_score(0, N-1) - sum(A)

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(1, N):
  for j in range(i-1, -1, -1):
    dp[i][j] = max(A[i]-dp[i-1][j], A[j]-dp[i][j+1])

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
d = dict()
for i in range(N):
    for j in range(N-i):
        span = (j,j+i+1)
        if i == 0:
            d[span] = As[j]
        else:
            d[span] = max(As[j]-d[(j+1,j+i+1)], As[j+i]-d[(j,j+i)])
print(d[span])

Submission status: Time Limit Exceeded

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

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j][0] = score[i][j-1][1] + As[j]
      else:
        score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      else:
        score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

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

Submission status: Time Limit Exceeded

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


# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      score[i][j][0] = score[i][j-1][1] + As[j]
      score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

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

Submission status: Time Limit Exceeded

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


# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(N):
    # if k == 0:
    #   continue
    j = i + k
    if j >= N:
      # 幅をとりすぎたら中断
      break
    if i == N - 1:
      score[i][j][0] = score[i][j-1][1] + As[j]
      score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

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