Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
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))

Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
d = [None]*(n+1)**2
def judge(l,r):
  if l >= r:
    return a[l]
  v = l + r*(n+1)
  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))


Fixed submission:
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])

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

print(judge(0,n-1))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
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))


Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):
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))

Fixed submission:
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])