Problem:


Score : 100 points

Problem Statement

Taro and Jiro will play the following game against each other.

Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N).
Until a becomes empty, the two players perform the following operation alternately, starting from Taro:

Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.

Let X and Y be Taro's and Jiro's total score at the end of the game, respectively.
Taro tries to maximize X - Y, while Jiro tries to minimize X - Y.

Assuming that the two players play optimally, find the resulting value of X - Y.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the resulting value of X - Y, assuming that the two players play optimally.

Sample Input 1

4
10 80 90 30

Sample Output 1

10

The game proceeds as follows when the two players play optimally (the element being removed is written bold):

Taro: (10, 80, 90, 30) → (10, 80, 90)

Jiro: (10, 80, 90) → (10, 80)

Taro: (10, 80) → (10)

Jiro: (10) → ()

Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100.

Sample Input 2

3
10 100 10

Sample Output 2

-80

The game proceeds, for example, as follows when the two players play optimally:

Taro: (10, 100, 10) → (100, 10)

Jiro: (100, 10) → (10)

Taro: (10) → ()

Here, X = 10 + 10 = 20 and Y = 100.

Sample Input 3

1
10

Sample Output 3

10

Sample Input 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Sample Output 4

4999999995

The answer may not fit into a 32-bit integer type.

Sample Input 5

6
4 2 9 7 1 5

Sample Output 5

2

The game proceeds, for example, as follows when the two players play optimally:

Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)

Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)

Taro: (2, 9, 7, 1) → (2, 9, 7)

Jiro: (2, 9, 7) → (2, 9)

Taro: (2, 9) → (2)

Jiro: (2) → ()

Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13.



Sample input:
4
10 80 90 30


Sample output:
10

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC L

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
dp = [[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
    for r in range(l+1,n+1):
        if (n - (r-l)) % 2 == 0:
            dp[l][r] = max(dp[l+1][r] + a[l],dp[l][r-1] + a[r-1])
        else:
            dp[l][r] = min(dp[l+1][r] - a[l], dp[l][r-1] - a[r-1])
print(dp[0][-1])

Submission status: Accepted

Solution code:
def f(A):
    # Taro (X) first  maximize X
    # Jiro (Y) second maximize Y
    # choose: first OR last
    # [ n m p q] => X=max | n + F(i + 1 + 1, j) + F(i + 1, j - 1)
    #                     | q + F(i, j - 1 - 1) + F(i + 1, j - 1)
    n = len(A)
    dp = [ [(0, 0)] * n for _ in range(n) ]
    for b in range(n - 1, -1, -1):
        for e in range(b, n):
            L1, L2 = dp[b + 1][e] if b + 1 <= e else (0, 0)
            R1, R2 = dp[b][e - 1] if b <= e - 1 else (0, 0)
            if A[b] + L2 > A[e] + R2:
                dp[b][e] = (A[b] + L2, L1)
            else:
                dp[b][e] = (A[e] + R2, R1)
    X, Y = dp[0][n - 1]
    return X - Y

assert f([10, 80, 90, 30]) == 10
assert f([10, 100, 10]) == -80
assert f([1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1]) == 4999999995
assert f([4, 2, 9, 7, 1, 5]) == 2
assert f([10]) == 10

n = input()
A = list(map(int, input().split()))
ans = f(A)
print(ans)

Submission status: Accepted

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

for w in range(1,n+1):
#for w in range(1,3,1):
#    print(dp[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()
#for i in dp:
#    print(i)
print(dp[0][n])

Submission status: Accepted

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 d in range(1,n):
    for j in range(n-d):
        if d%2 == 1:#最後打たない方
            dp[j][j+d] = min(dp[j][j+d-1]-a[j+d],dp[j+1][j+d]-a[j])
        else:#最後打つ方
            dp[j][j+d] = max(dp[j][j+d-1]+a[j+d],dp[j+1][j+d]+a[j])
if n%2==1:
	 print(dp[0][n-1])
else:
  	print(-dp[0][n-1])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = tuple(int(x) for x in input().split())

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l * n + r] = max(a[l] - memo[(l + 1) * n + r], a[r] - memo[l * n + r - 1])

    print(memo[n - 1])


if __name__ == '__main__':
    main()

# 連投の結果分かったこと
#
# [1]
# memoの初期化
# None => 530 ms
# 0 => 290 ms
# メモ化する配列の初期値が違うだけで、速度に大差
# Noneで初期化すると、代入時にint型に直すような処理が入るのか？
#
# [2]
# if __name__ == '__main__':
# なくすと遅くなった
# 530 ms -> 615 ms
#
# [3]
# map(int, input().split())
# int(x) for x in input().split()
# 数 msの違い？
#
# [4]
# メモ化配列の一次元化
# 287 ms よりこのコードが速ければ、一次元化した方がよい

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = tuple(int(x) for x in input().split())

    memo = tuple([0] * n for _ in range(n))
    for i in range(n):
        memo[i][i] = a[i]

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

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


if __name__ == '__main__':
    main()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# Noneではなく、0で初期化する

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = tuple(int(x) for x in input().split())

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

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


if __name__ == '__main__':
    main()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# 関数名は関係あるのか？

Submission status: Accepted

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

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

for l in range(n - 2, -1, -1):
    for r in range(l + 1, n):
        memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

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

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# if __name__ == '__main__':を辞めた

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = tuple(int(x) for x in input().split())

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[l] - memo[l + 1][r], a[r] - memo[l][r - 1])

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


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# maxの引数の順番を変えた

Submission status: Accepted

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

# 下記提出と全く同じ内容で提出します
# https://atcoder.jp/contests/dp/submissions/6590284

# これまでの連投で参考にしていたコード
# ほぼ同じ内容で提出しているつもりなのに、速度差が一向に縮まらない

# maxの引数の順番が自分と違うのが速度差の原因？

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = tuple(int(x) for x in input().split())

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# enumerateを辞めた

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = list(int(x) for x in input().split())

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

# listにした

Submission status: Accepted

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

    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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


if __name__ == '__main__':
    solve()

# [l,r]を
# l:=配列aの右端から左にシフト
# r:=lと一致する位置からn-1まで右にシフト
# と考えると、l==rは既にメモ化済みなので、l=n-2以前、r=l+1以降を調べればよい
# 漸化式で使う値は、
# lがより右にいるときの計算結果（前のループで計算済み）と
# rがより左にいるときの計算結果（一番左でもl==rなので計算済み）
# なので、参照する値がNoneになることはなく、Noneのチェックは不要になる

Submission status: Accepted

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

    for l in range(n - 1, -1, -1):
        for r in range(l, n):
            if memo[l][r] is None:
                memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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

Submission status: Accepted

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

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

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

Submission status: Accepted

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: Accepted

Solution code:
N = int(input())
A = [int(i) for i in 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+1-l):
        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)
print(dp[0][N])

Submission status: Accepted

Solution code:
from numpy import*
n,a=open(0)
n=int(n)
a=int64(a.split())
dp=zeros((n+1,n+1),'i8')
for k in range(1,n+1):
    i=arange(n-k+1)
    j=i+k
    dp[i,j]=amin(vstack((dp[i+1,j]-a[i],dp[i,j-1]-a[j-1])),0)if(n-k)%2else amax(vstack((dp[i+1,j]+a[i],dp[i,j-1]+a[j-1])),0)
print(dp[0,n])

Submission status: Accepted

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

from collections import deque

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

"""
・x < M > y → x+y-Mに取り替える
・V字型に帰着
・貪欲

"""

B = deque() # 修正後
for a in A:
    B.append(a)
    while True:
        if len(B) < 3:
            break
        x,y,z = B[-3], B[-2], B[-1]
        if x <= y >= z:
            B.pop()
            B.pop()
            B[-1] = x + z - y
            continue
        break

pts = [0,0]
player = 0
while B:
    if B[0] > B[-1]:
        pts[player] += B[0]
        B.popleft()
    else:
        pts[player] += B[-1]
        B.pop()
    player ^= 1

answer = pts[0] - pts[1]
print(answer)

Submission status: Accepted

Solution code:
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(int, read_line().split(' ')))[:n]


def read_float(n):
    return list(map(float, 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)]
    for i in range(len(dp)):
        dp[i][i] = a[i]
    for l in range(n - 2, -1, -1):
        for r in range(l + 1, n):
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    return dp[0][n - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()], dtype=np.int64)

s = np.copy(a)
for i in range(1, n):
    s = np.maximum(a[:n-i]-s[1:n-i+1], a[i:]-s[:n-i])

print(s[0])