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


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

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


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

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
d={}
def k(a):
      return ','.join(map(str,a))
def dp(a):
      ka=k(a)
      if ka in d:
            return [d[ka][0],d[ka][1]]
      if len(a)==1:
            d[ka]=[a[0],[]]
            return a[0],[]
      elif len(a)==2:
            d[ka]=[max(a),[min(a)]]
            return max(a),[min(a)]
      else:
            if a[0]-dp(a[1:])[0]>a[-1]-dp(a[:-1])[0]:
                  d[ka]=[a[0],a[1:]]
                  return a[0],a[1:]
            else:
                  d[ka]=[a[-1],a[:-1]]
                  return a[-1],a[:-1]
x,y=0,0
while a!=[]:
      x_,a=dp(a)
      x+=x_
      if a==[]:
            break
      y_,a=dp(a)
      y+=y_
print(x-y)


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