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:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*(n+2) for _ in range(n+2)]
# aiからajのX−Yの最大値
# [左端,右端)=[l,r)からの遷移    
# 左をとる[l+1,r)、右をとる[l,r−1)の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]=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:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[0]*(N+1) for _ in range(N+1)]

    for w in range(1, N+1):
        for le in range(N):
            ri = le + w
            if N < ri:
                break
            if N % 2 == w % 2:
                # 先手番
                dp[le][ri] = max(dp[le + 1][ri] + A[le],
                                 dp[le][ri - 1] + A[ri - 1])
            else:
                # 後手番
                dp[le][ri] = min(dp[le + 1][ri] - A[le],
                                 dp[le][ri - 1] - A[ri - 1])

    print(dp[0][N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)

n=int(inp())
ar=lis()
dp=[[0 for _ in range(n+5) ] for i in range(n+5)]
for i in range(n):
    dp[i][i]=ar[i]






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


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

Submission status: Accepted

Solution code:
dp={}
n=int(input())
nums=list(map(int,input().split()))
#print(dp)
#print(recursive(0,n-1))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(i,n,1):
        dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
print(dp[0][n-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()

dp = zeros((N + 1, N + 1))

from numba import njit


@njit('(i8,i8[:],i8[:,:])', cache=True)
def solve(N, A, dp):
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A, dp)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()


from numba import njit


@njit('(i8,i8[:])', cache=True)
def solve(N, A):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()

dp = full((N + 1, N + 1), -10**11)
dp[np.arange(N + 1), np.arange(N + 1)] = 0

from numba import njit


@njit('(i8,i8[:],i8[:,:])', cache=True)
def solve(N, A, dp):
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A, dp)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[0]*(2*N) for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
    dp[i][i+N] = -a[i]

for i in range(1, N+1):
    for x in range(N-i):
        dp[x][x+i] = max(a[x]+dp[x+1][x+i+N], a[x+i]+dp[x][x+i-1+N])
        dp[x][x+i+N] = min(dp[x+1][x+i]-a[x], dp[x][x+i-1]-a[x+i])
ans = dp[0][N-1]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)
dp=np.full((N,N),-1,dtype=np.int64)
for i in range(N):
    dp[i][i]=a[i]

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,a):
    if dp[i][j]!=-1:
        return dp[i][j]
    dp[i][j]=max(a[i]-calc(i+1,j,dp,a),a[j]-calc(i,j-1,dp,a))
    return dp[i][j]

calc(0,N-1,dp,a)
print(dp[0][N-1])

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
dp=[[0]*n for i in range(n)]
for i in range(n):
    if (n-1)%2==0:
        dp[i][i]=lis[i]
    else:
        dp[i][i]=-lis[i]
#print(dp)
for i in range(n-1,-1,-1):
    for j in range(n):
        #print(i,j)
        if i>=j:
            continue
        else:
            if (n-j+i-1)%2==0:
                if i+1>=n:
                    dp[i][j]=dp[i][j-1]+lis[j]
                elif j-1<0:
                    dp[i][j]=dp[i+1][j]+lis[i]
                else:
                    dp[i][j]=max(dp[i+1][j]+lis[i],dp[i][j-1]+lis[j])
            else:
                if i+1>=n:
                    dp[i][j]=dp[i][j-1]-lis[j]
                elif j-1<0:
                    dp[i][j]=dp[i+1][j]-lis[i]
                else:
                    dp[i][j]=min(dp[i+1][j]-lis[i],dp[i][j-1]-lis[j])
    #print(dp)
print(dp[0][-1])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

prev = [a*(1 if N%2 else -1) for a in A]
  
phase = N
while phase > 1:
  phase -= 1
  now = []
  for i in range(phase):
    if phase%2:
      now.append(max(prev[i]+A[i+N-phase],prev[i+1]+A[i]))
    else:
      now.append(min(prev[i]-A[i+N-phase],prev[i+1]-A[i]))
  prev = now[:]

print(prev[0])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/08/2020

from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

n = ii1()
arr = iia()
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1)[::-1]:
    for j in range(i, n + 1):
        if i == j:
            dp[i][j] = arr[i - 1]
        else:
            dp[i][j] = max(arr[i - 1] - dp[i + 1][j], arr[j - 1] - dp[i][j - 1]
        )
print(dp[1][-1])

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
i=j=n-1
for i in range(n-1,-1,-1):
    for j in range(1,n+1):
        if i>j-1:
            continue
        if ((j-i)%2)^(n%2):
            dp[i][j] = min(-arr[i]+dp[i+1][j],-arr[j-1]+dp[i][j-1])
        else:
            dp[i][j] = max(arr[i]+dp[i+1][j],arr[j-1]+dp[i][j-1])
print(dp[0][n])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
  if (N-1)%2==0:
    dp[i][i] = A[i]
  else:
    dp[i][i] = -A[i]
for k in range(1,N):
  for i in range(N):
    j = i+k
    if j>N-1:
      break
    if (N-(k+1))%2==0:
      dp[i][j] = max(dp[i][j-1]+A[j],dp[i+1][j]+A[i])
    else:
      dp[i][j] = min(dp[i][j-1]-A[j],dp[i+1][j]-A[i])
ans = dp[0][N-1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    for l in range(n+1):
        r=i+l
        if r>n:
            continue
        if (n-i)%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][n])

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
for k in range(1,n+1):
    for i in range(n+1-k):
        if (n-k)%2==0:
            dp[i][i+k] = max(dp[i+1][i+k] + A[i], dp[i][i+k-1] + A[i+k-1])
        else:
            dp[i][i+k] = min(dp[i+1][i+k] - A[i], dp[i][i+k-1] - A[i+k-1])
print(dp[0][n])

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

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

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

    for k in range(1, N):  # distance
        for i in range(N):  # start grid
            if i + k >= N:
                break
            dp[i][i + k] = max(A[i + k] - dp[i][i + k - 1], A[i] - dp[i + 1][i + k])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    su = [0 for _ in range(n + 1)]    
    for l in range(n):
        su[l + 1] = su[l] + a[l]

    INF = 1e18
    dp = [[-INF for _ in range(n + 1)] for _ in range(n + 1)]

    for l in range(n + 1):
        dp[l][l] = 0
    for length in range(1, n + 1):
        l = 0
        while l + length <= n:
            r = l + length
            dp[l][r] = max(a[l] + (su[r] - su[l + 1]) - dp[l + 1][r], 
                            a[r - 1] + (su[r - 1] - su[l]) - dp[l][r - 1])
            l += 1
    print(dp[0][n] - (su[n] - dp[0][n]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(a,i,j,dp):
    if dp[i][j]==-1:
        if i>j:
            return 0

        dp[i][j]=max(a[i]+min(f(a,i+2,j,dp),f(a,i+1,j-1,dp)),
                                a[j]+min(f(a,i+1,j-1,dp),f(a,i,j-2,dp)))
    return dp[i][j]
        
n=int(input())
dp=[[-1 for i in range(n)] for j in range(n)]
a=list(map(int,input().split()))
for i in range(n):
    dp[i][i]=a[i]

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

s1=f(a,0,n-1,dp)

print(s1-sum(a)+s1)

Submission status: Accepted

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

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

# dp[l][r] = [l:r)の区間から起こり得るX - Yの最大値
# [N - 区間の長さ] = 偶数のとき、次に取るのは先手

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

for k in range(1, N + 1): # 区間の長さ
  for i in range(N + 1 - k):
    if (N - k) % 2 == 0: # 先手番
      dp[i][i + k] = max(dp[i + 1][i + k] + A[i], dp[i][i + k - 1] + A[i + k - 1])
    else: # 後手番
      dp[i][i + k] = min(dp[i + 1][i + k] - A[i], dp[i][i + k - 1] - A[i + k - 1])

print(dp[0][N])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n-t+1) for t in range(1, n+1)]
dp[0] = a
for t in range(1, n):
    for i in range(n-t):
        dp[t][i] = max(-dp[t-1][i+1] + a[i], -dp[t-1][i] + a[i+t])
print(dp[n-1][0])

Submission status: Accepted

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

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

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

# [i,j)
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])

Submission status: Accepted

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

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

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

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

    print(dp[0][N])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Solution code:
import sys

stdin = sys.stdin


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


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


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


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
a_array = na()

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

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

Submission status: Accepted

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

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

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

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

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

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

        points.pop()

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

main()

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
A = iInLH()

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

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[-1 for i in range(3010)] for j in range(3010)]
for i in range(3010):
    dp[i][i] = 0
for len in range(1, N+1):
    for i in range(N - len + 1):
        j = i + len
        if (N - len) % 2 == 0: # 前が誰の手番であったか
            # 先手番
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1]) # lenが1つ短いものから遷移

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