[LeetCode] 121. Best Time to Buy and Sell Stock

카데인 알고리즘 사용하여 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0               # profit은 항상 0보다 커야함
        min_price = float("inf") 
        
        for price in prices:
            min_price = min(min_price, price)       # 현재 값과 기존 최소값 비교
            profit = max(profit, price - min_price) # (현재 값 - 기존 최소값)과 기존 profit 비교
        
        return profit

최대 서브 배열 문제를 푸는 카데인 알고리즘을 사용하여 풀 수 있다.
다만, 서브 배열의 합이 아닌 최고점과 최저점의 차이라는 부분만 다르다.

1. 배열의 앞쪽부터 순회하며 현재값과 현재까지 최소값을 비교
2. 현재의 profit과 (현재값) - (기존 최소값) 중 큰 값을 profit으로
3. 마지막에 profit 리턴

• 문제: Best Time to Buy and Sell Stock