Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache
 
    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
        self.n = len(prices)
    
    @lru_cache(None)
    def transaction(self, money, stock, i, last_buy):
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock,_money = stock,money

        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            self.transaction(money, stock, i + 1, self.prices[i])
        # backtracking
        money,stock = _money,_stock
 
        ## sell
        if stock > 0 and self.prices[i] > last_buy:
            stock, money = 0, stock * self.prices[i] + money
            if money > 1000:
                self.transaction(money, 0, i + 1,0)
        # backtracking
        money,stock = _money,_stock
 
        ## do nothing
        self.transaction(money, stock, i + 1,last_buy)
 
 
def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0, 0)
    print(solver._max)
    

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i, _inner_max):
        if stock == 0 and money < _inner_max - 1:
            return
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > _inner_max:
                _inner_max = money
                self.transaction(money, 0, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1, _inner_max)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0,1000)
    print(solver._max)
    

if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i):
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > 1000:
                self.transaction(money, 0, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0)
    print(solver._max)
    

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


if __name__ == "__main__":
    main()