99클럽 코테 스터디 42일차 TIL + 리트코드 DP

 

- 주제 : 동적계획법

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

- 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price 
            elif price - min_price > max_profit:
                max_profit = price - min_price  

        return max_profit

 

반복문으로 최소 값을 min_price에 저장하고, 가능한 최대 이익을  max_profit로 계산해서 배열 순회시킴
시간복잡도  : O(n)