Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = {}

def dp(i, j, turn = 1):
    if i == j: return 0
    if (i,j) in MEMO: return MEMO[(i,j)]

    xy1 = dp(i, j-1, -turn) + turn*A[j-1]
    xy2 = dp(i+1, j, -turn) + turn*A[i]
    res = xy1 if turn*xy1 > turn*xy2 else xy2
    MEMO[(i,j)] = res
    return res

print(dp(0, len(A), 1))


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = {}

def dp(i, j, turn = 1):
    if i == j: return 0
    if (i,j) in MEMO: return MEMO[(i,j)]

    xy1 = dp(i, j-1, -turn) + turn*A[j-1]
    xy2 = dp(i+1, j, -turn) + turn*A[i]
    res = xy1 if turn*xy1 > turn*xy2 else xy2
    MEMO[(i,j)] = res
    return res

print(dp(0, len(A), 1))


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])