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

- Problem

121. Best Time to Buy and Sell Stock

헐 값에 사서(i-th day), 떡상할 때 팔자(j-th day) (i < j)

단순하게 배열에서 최소 값과 최대 값을 이용하여 가장 큰 차익을 찾는다면 잘못된 방법이다.
예를 들어, prices=[5,4,3,2,1]이라는 배열이 주어졌을 때 최소 값은 1, 최대 값을 5이다.
그러나 이를 코드에 그대로 반영한다면, 1원(5일 째)에 사서 5원(1일 째)에 파는 것이다.

- 내 풀이 (DP)

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

        for price in prices:
            if price < min_price:
                min_price = price
            
            else:
                max_profit = max(max_profit, price - min_price)
            
        return max_profit

- 결과