Best Time to Buy and Sell Stock

Problem Id: 121 Difficulty: Easy Tag: Array Tag: Dynamic Programming


Intuition

For each node, if we sold out the stack at that moment, to get the most profit, we need to buy it on the minimum point which is in previous of the current time. So we could use this principle to solve this problem in one loop.

Solution


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        max_profit = 0
        min_prev = prices[0]
        for p in prices:
            max_profit = max(p - min_prev, max_profit)
            min_prev = min(min_prev, p)
        return max_profit