내가 정말정말 어려워하는 DP.. DP의 벽을 깨보고자 리트코드의 DP 문제들을 하나씩 해결해보려고 한다. 당분간은 DP의 늪에 빠져 있을 듯 하다. 🤪

DP 문제들 다 깨버릴테다.. 😂⛏

121. Best Time to Buy and Sell Stock

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = [0] * len(prices)
        maximumProfit = 0
        
        for i in range(1,len(prices)) :
            profit[i] = prices[i] - min(prices[:i])
            if (profit[i] > maximumProfit) : maximumProfit = profit[i]
                
        return maximumProfit

Logic

사실 dp처럼 안 풀어도 되는 문제같지만 dp같이 풀어보았다. prices의 길이만큼 profit 배열을 선언한다. maximumProfit은 먼저 0으로 초기화한다.

1부터 prices의 길이 -1까지 순회하면서 인덱스가 0 ~ i-1인 원소 중에 최소값을 찾아 prices[i]에서 뺀 값을 profit[i]에 할당한다. 생각해보니 최솟값은 갱신되는 값이라서 아예 fix해도 되는 값이군.. 만약 maximumProfit보다 크다면 업데이트하고 최종적으로 maximumProfit를 리턴한다.

문제 출처

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