Solutions

# Brute force, sliding window or dynamic programming. Keep track of the lowest price and the maximum profit at each step. 
# sliding-window

# Brute force - O(n^2) time, O(1) space
def maxProfit(prices: list[int]) -> int:
    maxp = 0
    for i in range(len(prices)):
        buy = prices[i]
        for j in range(i, len(prices)):
            maxp = max(maxp, prices[j] - buy)
    return maxp


# Sliding window - O(n) time, O(1) space
def maxProfit2(prices: list[int]) -> int:
    l = 0
    maxprofit = 0
    for r in range(1, len(prices)):
        curr = prices[r]
        if curr >= prices[l]:
            maxprofit = max(maxprofit, curr - prices[l])
        else:
            l = r
    return maxprofit


# Dynamic programming - O(n) time, O(1) space
def maxProfit(prices: list[int]) -> int:
    maxprofit = 0
    buyprice = 9999999
    for p in prices:
        buyprice = min(p, buyprice)
        maxprofit = max(maxprofit, p - buyprice)
    return maxprofit