(LeetCode)121. 주식을 사고팔기 가장 좋은 시점

문제

Best Time to Buy and Sell Stock - LeetCode

아이디어

  • 카데인 알고리즘 적용

코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        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)에 풀이
  • 카데인 알고리즘은 부분합구하는 문제에서 많이 쓰이는 알고리즘이니 잘 알아둘것