---
# System prepended metadata

title: Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
tags: [Leetcode(C++)]

---

# Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 。

想法 : 

    DP最難的就是尋找最優子結構與轉移方程，連日來被電的飛起。
    
    Step 1 :
    
        首先，有三種狀態 : 
        buy(i)  = max(rest(i - 1) - price[i] , buy(i - 1));
        sell(i) = max(buy(i - 1) + price[i] , sell(i - 1));
        rest(i) = max(rest(i - 1) , sell(i - 1) , buy(i - 1));
    
        buy(i) :  第i天買，或是不買。 
        sell(i) : 第i天賣，或是不賣。 
        rest(i) : 第i天休息。 
    
    Step 2 :
    
        觀察一下，發現可以簡化 : 
        rest(i) = sell(i-1);
        為什麼? 因為賣掉那天肯定是最大的，就算沒賣也是sell(i-1) >= rest(i-1)。
        
    Step 3 :
    
        帶回原式將rest()替換掉 :
        buy(i) = max(sell(i - 2) - price[i], buy(i - 1));
        sell(i) = max(buy(i-1) + price[i] , sell(i - 1));
        
    Step 4 :
    
        注意初始設值與邊界狀態。
        第一天不可能賣、可能買第一天或是買第二天、可能第二天賣掉。

時間複雜度 : O(n)。

程式碼 :

```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int l = prices.size(), sell_2 ,sell_1, sell, buy_1, buy;
        
        if(l == 1) return 0;    
        if(l == 2) return max(-1 * prices[0] + prices[1], 0);
        
        sell_2 = 0;
        sell_1 = max(sell_2 , -1 * prices[0] + prices[1]);
        buy_1 = max(-1 * prices[0] , -1 * prices[1]);
        
        for(int i = 2 ; i < l ; i++){
            buy = max(sell_2 - prices[i], buy_1);
            sell = max(buy_1 + prices[i], sell_1);
            
            buy_1 = buy;
            sell_2 = sell_1;
            sell_1 = sell;
            
            //cout << buy_1 << " " << buy << " ; " << sell_2 << " " << sell_1 << " " << sell << endl; 
        }
        
        return sell;
    }
};
```