[leetcode 309] Best Time to Buy and Sell Stock with Cooldown

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

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

 

풀이:

아..너무 어렵다 dp..

처음 접근을 가지치기를 해보았다. 가지치기를 하면 선택지가 정해져있다. 목적은 최대 이윤을 남기는 것

buy[i]는 i번째에서 buy상태일 때 얻을 수 있는 최대 이익

sell[i]는 i번째에서 sell상태일 때 얻을 수 있는 최대 이익

rest[i]는 i번째에서 cool down상태일 때 얻을 수 있는 최대 이익 

 

- buy[i] =  max(buy[i-1], rest[i-1] -price[i])

 쿨다운한 상태, 즉 이전 buy를 그대로 가져오거나 cool down에서 buy로 상태 변화

- sell[i] = max(sell[i-1], buy[i-1] + price[i])

이전 sell 상태이거나 buy후에 sell

- rest[i] = max(buy[i-1], sell[i-1], rest[i-1])

이전 buy 상태 2. 이전 sell 상태 3. 쿨다운 유지

이 된다.

 

여기서 항상 buy[i] <= rest[i] <= sell[i]이므로 rest[i]는 항상 sell[i-1]일 것이다.

 

정리하자면 

buy[i] =  max(buy[i-1], rest[i-1] -price[i])

sell[i] = max(sell[i-1], buy[i-1] + price[i])

rest[i] = sell[i-1] 이 된다.

 

코드로 풀어보자.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
     
        int n= prices.size();
        
        if(n<2) return 0;
        
        int buy[n];
        int sell[n];
        int rest[n];
        buy[0] = -prices[0], sell[0] = 0, rest[0] = 0;
        
        for(int i=1; i<n; i++){
            buy[i] = max(buy[i-1], rest[i-1]-prices[i]);
            sell[i] = max(sell[i-1], buy[i-1] + prices[i]);
            rest[i] = sell[i-1];
        }
        
        return sell[n-1];
    }
};

 

사실 배열이 필요 없는 것을 알 수 있다. 이전 값만 변수에 저장해도 가능.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
     
        int n= prices.size();
        if(n<2) return 0;
      
        int prev_buy = -prices[0], prev_sell = 0, prev_rest=0;
        int cur_sell, cur_buy, cur_rest;
        for(int i=1; i<n; i++){
            cur_buy = max(prev_buy, prev_rest-prices[i]);
            cur_sell = max(prev_sell, prev_buy + prices[i]);
            cur_rest = prev_sell;
            
            prev_buy = cur_buy;
            prev_sell = cur_sell;
            prev_rest = cur_rest;
            
        }
        return cur_sell;
    }
};