121. Best Time to Buy and Sell Stock

Information

  • Diffculty: Easy

  • Created: 2020-03-11 08:14:00

  • Last Motified: 2020-03-11 08:19:01

  • Tags: Array, 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