Skip to main content

121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

Python​

Top Down DP​

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[n][0] as buy price
        # dp[n][1] as profit
        dp = [[0, 0] for _ in range(len(prices) + 1)]

        dp[0][0] = float('-inf')

        for i, price in enumerate(prices, start=1):
            dp[i][0] = max(dp[i-1][0], -price)
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + price)

        return dp[-1][1]

Top Down DP - Single Variable​

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        buy_price = None

        for price in prices:
            buy_price = price if buy_price is None else min(price, buy_price)
            max_profit = max(max_profit, price - buy_price)

        return max_profit

Go​

func maxProfit(prices []int) int {
    max_profit := 0
    buy_price := prices[0]

    for _, price := range prices {
        if (price < buy_price) {
            buy_price = price
        }

        if (price - buy_price > max_profit) {
            max_profit = price - buy_price
        }
    }
    return max_profit
}