[Python] LeetCode 121 Best Time to Buy and Sell Stock (DP)

📌 문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

예제 1

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

예제 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

조건

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

📌 풀이

👆 첫 번째 시도 (시간초과)

• profit : i번째 날에 팔았을 때 얻을 수 있는 최대 수익
• (i번째 날의 가격) - (0~i-1번째 날 중 가격이 가장 낮았던 날의 가격)을 profit에 저장하되 해당 값이 음수이면 0을 저장한다.
• price[0:i]로 슬라이싱하는 부분에서 시간초과가 났다.

class Solution(object):
    def maxProfit(self, price):
        profit = [0] * len(price)
        
        for i in range(1, len(price)):
            profit[i] = max(0, price[i] - min(price[0:i]))
        
        return max(profit)

✌ 두 번째 시도 (성공)

• profit : i번째 날에 팔았을 때 얻을 수 있는 최대 수익
• minprice[i] : 0~i-1번째 날 중 가격이 가장 낮았던 날의 가격
• 위의 방법과 아이디어는 동일하나 minprice를 슬라이싱이 아닌 원소비교로 변경했다.

class Solution(object):
    def maxProfit(self, price):
        
        if len(price) == 1:
            return 0
        elif len(price) == 2:
            return max(0, price[1] - price[0])
        else:
            minprice = [0] * len(price)
            profit = [0] * len(price)
            
            minprice[0] = 0
            profit[0] = 0
            
            minprice[1] = price[0]
            profit[1] = max(0, price[1] - minprice[1])

            for i in range(2, len(price)):
                minprice[i] = min(minprice[i-1], price[i-1])
                profit[i] = max(0, price[i] - minprice[i])

            return max(profit)

그치만 효율적이지 않아 다시 풀고 싶었다 -.- 문제를 다시 읽어보다가 이건 굳이 DP로 풀 필요가 없다는 걸 알았다.

✌ 세 번째 시도 (성공)

• minprice : 0~i번째 날 중 가격이 가장 낮은 날의 가격
• 0 <= prices[i] <= 10^4라는 조건이 주어졌으므로 minprice를 price의 최댓값인 10^4로 초기화하고 for문을 돌면서 업데이트해준다.

class Solution(object):
    def maxProfit(self, price):
        
        minprice = 10000
        profit = 0
        
        for i in price:
            profit = max(profit, i - minprice)
            if i < minprice:
                minprice = i
            
        return profit

편-안