[LeetCode] Medium - 309 Best Time to Buy and Sell Stock with Cooldown

▶309 - Best Time to Buy and Sell Stock with Cooldown

▶문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

▶예제

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

 

Input: prices = [1]
Output: 0

 

▶풀이

dp1에는 더해지는 값들을 넣어준다.

그래서 이전 값과 증가된 수치를 더해서 넣어주거나, 아님 이전에 동결된 값을 넣어준다.

 

dp2에는 주식을 판 값을 유지해야 하기에, dp1에서 이전 값과, dp2에서 이전 값 중 큰 값을 넣어준다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        dp1 = [0 for _ in range(len(prices))]
        dp2 = [0 for _ in range(len(prices))]
        for i in range(1, len(prices)):
            dp1[i] = max(dp1[i - 1] + prices[i] - prices[i - 1], dp2[i - 1])
            dp2[i] = max(dp1[i - 1], dp2[i - 1])

        return max(dp1[-1], dp2[-1])