[알고리즘] 주식을 사고팔기 가장 좋은 시점

주식을 사고팔기 가장 좋은 시점

내 풀이

def maxProfit(prices: List[int]) -> int:
    max_profit = -sys.maxsize

    for i in range(len(prices)-1):
        tmp_max = max(prices[i+1:]) - prices[i]
        max_profit = max(max_profit, tmp_max)

    if max_profit > 0:
        return max_profit
    else:
        return 0

시간초과가 났다. O(n^2)이기 때문이다.

책 풀이

    profit = 0
    min_price = sys.maxsize

    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)

    return profit

O(n)으로 돌면서 지나온 값들에 대해 min_price들을 갱신해준다. 그리고 마찬가지로 현재 가격에서 min_price 를 뺸 값과 profit을 비교해 최대값을 갱신해준다.