릿코드 121. Best Time to Buy and Sell Stock

이 글은 Tistory에서 이전된 포스팅입니다. 원본은 여기에서 확인할 수 있습니다.

문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

저점(buy), 고점(sell)을 변수로 두고 생각했는데 O(n^2) 밖에 안떠올랐고 Discussion 열어봤다.

저점이 바뀔 때,

1. 저점 뒤에(저점보다 늦은 시간에) 고점이 온다면, 이전의 저점이 더 큰 profit을 볼 일은 없다.

2. 저점 앞에 고점이 있었다면, 이전 저점과 고점에 따른 profit을 기억해둔다. 그리고 고점은 저점 뒤에 있어야 하므로 바뀐 저점에 고점을 같이 위치시킨다.

1을 확정하고 생각을 풀어나가면 떠올랐을 거 같다.

    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, profit = prices[0], prices[0], 0
        for i in range(1, len(prices)):
            val = prices[i]
            if val < buy:
                profit = max(profit, sell - buy)
                buy = val
                sell = val
            elif val > sell and val > buy:
                sell = val

        return max(profit, sell-buy)