leetcode 121 (easy)

문제

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

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minn = 10001
        profit = 0
        
        for price in prices:
            minn = min(minn,price)
            profit = max(price - minn,profit)
            
        return profit

O(n)의 풀이가 있을 것 같아서 그 부분을 고민했던 문제이다.
한번 스캔하면서 현 상태 까지의 min 값을 저장해두고, 매 시점마다 그때까지의 min과 그당시의 가격 비교를 통해 낼 수 있는 max profit을 저장해둔다.

이렇게 한번 쭉 읽으면 O(n)으로 풀이가 가능하다.