1. 문제

문제링크 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock

2. 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize

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

저점과 고점의 차가 가장 클 때 최대 수익이 된다. 이 풀이에선 min_price가 저점을 의미한다. for문에서 현재 가격과 저점을 비교하고 현재 가격이 더 낮으면 저점을 새로 갱신한다. profit은 현재 가격과 저점의 차를 구한 후 이전에 계산한 profit과 비교하며 갱신된다. prices 크기만큼 반복하므로 시간 복잡도는 $O(n)$이 된다.