Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000000


n = int(input())
a = list(map(int, input().split()))

dp = [[-1 for j in range(MAX + 1)] for i in range(n)]
dp[0][0] = 1000
for k in range(1, MAX + 1):
    if 1000 - a[0] * k < 0:
        break
    dp[0][k] = 1000 - a[0] * k
print(dp[0])
for i in range(1, n):
    for j in range(MAX + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        # 買うとき
        for k in range(1, MAX + 1):
            if j - k < 0:
                break
            # if dp[i - 1][j - k] - a[i] * k < 0:
            #     break
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - a[i] * k)
        # 売る時
        for k in range(1, MAX + 1):
            if j + k >= MAX + 1:
                break
            if dp[i - 1][j + k] < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i - 1][j + k] + a[i] * k)
    print(dp[i])
ans = max(dp[-1])
print(max(ans, 1000))
    # return max(ans, 1000)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = []
flag = True
for i in reversed(range(n)):
    if i == 0:
        if not flag:
            x.append(a[i])
        break
    flag2 = flag
    if flag:
        if a[i - 1] < a[i]:
            x.append(a[i])
            flag2 = not flag2
    else:
        if a[i - 1] > a[i]:
            x.append(a[i])
            flag2 = not flag2
    flag = flag2
x = x[::-1]
m = len(x)
if m % 2 == 1:
    x = x[1:]
# print("x =", x)
cur_money = 1000
cur_stock = 0
for i in range(m):
    if i % 2 == 0:
        cur_stock += cur_money // x[i]
        cur_money %= x[i]
    else:
        cur_money += x[i] * cur_stock
        cur_stock = 0
print(cur_money)

Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000000000


n = int(input())
a = list(map(int, input().split()))

dp = [[-1 for j in range(MAX + 1)] for i in range(n)]
dp[0][0] = 1000
for k in range(1, MAX + 1):
    if 1000 - a[0] * k < 0:
        break
    dp[0][k] = 1000 - a[0] * k
print(dp[0])
for i in range(1, n):
    for j in range(MAX + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        # 買うとき
        for k in range(1, MAX + 1):
            if j - k < 0:
                break
            # if dp[i - 1][j - k] - a[i] * k < 0:
            #     break
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - a[i] * k)
        # 売る時
        for k in range(1, MAX + 1):
            if j + k >= MAX + 1:
                break
            if dp[i - 1][j + k] < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i - 1][j + k] + a[i] * k)
    print(dp[i])
ans = max(dp[-1])
print(max(ans, 1000))
    # return max(ans, 1000)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = []
flag = True
for i in reversed(range(n)):
    if i == 0:
        if not flag:
            x.append(a[i])
        break
    flag2 = flag
    if flag:
        if a[i - 1] < a[i]:
            x.append(a[i])
            flag2 = not flag2
    else:
        if a[i - 1] > a[i]:
            x.append(a[i])
            flag2 = not flag2
    flag = flag2
x = x[::-1]
m = len(x)
if m % 2 == 1:
    x = x[1:]
# print("x =", x)
cur_money = 1000
cur_stock = 0
for i in range(m):
    if i % 2 == 0:
        cur_stock += cur_money // x[i]
        cur_money %= x[i]
    else:
        cur_money += x[i] * cur_stock
        cur_stock = 0
print(cur_money)