---
# System prepended metadata

title: 'LeetCode #309 [Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)'
tags: [LeetCode, Medium, Dynamic Programming]

---

###### tags: `LeetCode` `Dynamic Programming` `Medium`
# LeetCode #309 [Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)
### (Medium)
給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。​
設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票後，你無法在第二天買入股票 (即冷凍期為 1 天)。


---
動態規劃題
這題有三個狀態, hold, sell, cd, 彼此關係為:
* hold=max(hold, cd-prices[i])
* sell[i]=max(sell, hold+prices[i])
* cd[i]=max(cd, sell)

要注意hold的初始值為INT_MIN, sell與cd的初始值皆為0, 否則第一天的sell會變為prices[0]。


---
```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()>=2){
            int i=prices.size();
            int hold=INT_MIN, sell=0, cd=0;
            for(i=0;i<prices.size();i++){
                int hold2=hold, sell2=sell, cd2=cd;
                hold=max(cd2-prices[i],hold2);
                sell=max(sell2, hold2+prices[i]);
                cd=max(sell2, cd2);
            }
            return max(sell,cd);
        }
        return 0;
    }
};
```
