[LeetCode] 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

이번에는 최대 이득을 볼 수 있는 주식 매입/매도 시점을 찾는 문제이다.

원래 for 문을 2중으로 사용해야하지만, minimum price와 maximum profit을 저장해가면서 list 전체를 scan하면 O(n)으로 문제를 해결할 수 있다.

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

        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
        
        return max_profit