Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    readline = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if memo[l][r] != -1:
            return memo[l][r]
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )

        memo[l][r] = ret
        return ret

    memo = [[-1] * n for _ in range(n)]

    ret = calc()

    print(ret)


if __name__ == '__main__':
    main()


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

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    readline = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )
        return ret

    ret = calc()

    print(ret)


if __name__ == '__main__':
    main()


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l * n + r] is None:
        memo[l * n + r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l * n + r]


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

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

print(func(0, n - 1))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l][r] is None:
        memo[l][r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l][r]


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

print(func(0, n - 1))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人

    # if l == r:
    #     return a[l]
    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


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

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

print(func(0, n - 1))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    if l == r:
        return a[l]

    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    if l == r:
        return a[l]

    if memo[l][r] is not None:
        return memo[l][r]

    res = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro

    if l == r:
        return a[l] * (-1 if taro_turn is None else 1)

    if memo[l][r] is not None:
        return memo[l][r]

    if taro_turn is None:
        # jiro_turn
        res = min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        res = max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])

    memo[l][r] = res
    return res


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

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1, True))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro
    if l > r:
        return 0

    if taro_turn is None:
        # jiro_turn
        return min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        return max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])


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

print(func(0, n - 1, True))


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

Buggy python submission (verdict: Runtime Error):
def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro
    if l > r:
        return 0

    if taro_turn is None:
        # jiro_turn
        return min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        return max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])


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

print(func(0, n - 1, True))


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