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

gnlenfn·2021년 9월 26일
0

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

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 리턴

0개의 댓글