Best Time to Buy and Sell Stock

나의 논리

문제를 읽자마자 쉽네? 하고 어떻게 해야될지 생각해본 후
코드를 작성하고 제출했더니 시간초과였다.
C++에서는 시간초과 안될것 같은 코드가 파이썬에서는 가볍게 시간초과되서... 가끔 황당하기도 하지만
엄밀히 따지면 반복문 하나에, 리스트를 파라미터로 받는 max면
O(n^2)가 되지 않을까..

def maxProfit(self, prices: List[int]) -> int:
        
        ret = 0
        for i, price in enumerate(prices):
            temp_max = max(prices[i:])
            
            if temp_max > price and temp_max-price > ret :
                ret = temp_max - price
        
        return ret

그래서 O(n)시간복잡도를 가지는 알고리즘을 고민하다가
아이디어가 떠올랐는데 뭔가 아닌거같아서.. 멈췄다.

리스트의 원소들을 순회하면서 가장 작은 원소와 가장 큰 원소를 변수에 갱신한다는 알고리즘이었는데..
가장 작은 원소는 가장 큰 원소 앞에 있어야한다..
그런데 가장 작은 원소가 가장 큰 원소 뒤에 나올 수도 있잖아?
어떡하지? 하다가 시간을 많이 써서 그냥 답을 보기로 했는데
아차 너무 협소한 사고를 하고 있었다.. 답이랑 비슷한 알고리즘을 생각해낸것 같은데 아쉽다..

정답 논리

def maxProfit(self, prices: List[int]) -> int:
        
        ret = 0
        min_price = 987654321
        for price in prices:
            min_price = min(min_price, price)
            ret = max(ret, price - min_price)
            
        return ret