<p>You are given an array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day.</p>

<p>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:</p>

<ul>
	<li>After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).</li>
</ul>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,2,3,0,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> transactions = [buy, sell, cooldown, buy, sell]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 5000</code></li>
	<li><code>0 &lt;= prices[i] &lt;= 1000</code></li>
</ul>

// Idea: in this case, we have 4 case might show up
// buy, comes from cool state, goto holding or sell
// hodding, comes from buy stage, go to sell stage
// sell, comes from buy stage or hodding stage, go to cool stage
// cool, comes from sell stage or cool stage, go to cool stage or buy stage.

// p = 1 => b = -1, h = -1000, s = 0, c = 0
// p = 2 => b = -2, h = -1, s = -1 + 2 = 1, c = 0
// p = 3 => b = -3, h = -1, s = -1 + 3 = 2, c = 1
// p = 0 => b = 1 - 0 = 1, h = -1, s = -1 + 0 = -1, c = 2
// p = 2 => b = 2 - 2 = 0, h = 1, s = 1 + 2 = 3, c = 2

// [1, 4, 2]
// p = 1, b = -1, h = -1000, s= 0, c =0
// p = 4, b = -4, h = -1, s = -1 + 4 = 3, c = 0
// 

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = -1001, hold = -1001, sell = 0, cool = 0;
        int plen = prices.size();
        
        for(int i = 0; i< plen; i++) {
            int _buy = buy;
            int _hold = hold;
            int _sell = sell;
            int _cool = cool;

            buy = _cool - prices[i];
            hold = max(_hold, buy);
            sell = max(0, max(_buy, _hold) + prices[i]);
            cool = max(_cool, _sell);
        }

        return max(sell, cool);

    }
};
13600