<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>

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // dp[i][0] represents the maximum profit on day i when not holding a stock
        // dp[i][1] represents the maximum profit on day i when holding a stock
        vector<vector<int>> dp(n, vector<int>(2, 0));

        // Base cases
        dp[0][0] = 0;                // Not holding a stock on day 0
        dp[0][1] = -prices[0];       // Holding a stock on day 0 (bought it)

        for (int i = 1; i < n; ++i) {
            // If not holding a stock today, you could have:
            // - Not held a stock yesterday
            // - Sold a stock today
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);

            // If holding a stock today, you could have:
            // - Held a stock yesterday
            // - Bought a stock today (only if you were not holding a stock yesterday and were not in cooldown)
            // To handle cooldown, ensure that you only buy if you were not selling on the day before yesterday
            dp[i][1] = max(dp[i-1][1], (i >= 2 ? dp[i-2][0] : 0) - prices[i]);
        }

        // The maximum profit will be on the last day when not holding any stock
        return dp[n-1][0];
    }
};

14300