https://leetcode.com/problems/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:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

**Solution 1
**t is quite similar to balloon burst problem. We build a 2-dimension dp[][]. dp[left][right] indicates the max profit we can get from prices[left] to prices[right]. Because there is one day cool down, we can get the basic formula

**dp[left][right] = dp[left][k-1] + dp[k+1][right]**. It means when we sold at k-1 time, at most we can but at k+1 time.

Complete formula is

This solution takes O(n^2) time and space, which was not able to pass leetcode.

**Solution 2
**We define sell[] and notsell[]. sell[i] is the max profit if we sell at i time. notsell[i] is the max profit if we don’t sell at i time.

For** sell[i]**, If we sell at i time, at least we should add the gap value of **prices[i] – price[i – 1]**. It has 2 conditions. When i-1 time was sold, then buy at i-1 time again and sell it at i time.(or it equal we didn’t sell at i-1 time, we passed it). So we have **sell[i] = ****sell[i – 1] + prices[i] – price[i – 1].**

Another condition is that at i-1 time, we didn’t sell. We really bought at i-1 time and sell at i time. Because there is a cool down time. i-2 time shouldn’t sell neither. So for this condition we have **notsell[i – 2] +** **prices[i] – price[i – 1]**.

For **notsell[i]**, it is a easy one. **notesell[i] = max(sell[i – 1], notsell[i – 1])**

Totally, we have:

**sell[i] = max(****sell[i – 1] + prices[i] – price[i – 1], notsell[i – 1] + prices[i] – price[i – 1])
notesell[i] = max(sell[i – 1], notsell[i – 1])**

In the end, we return **max(sell[n – 1], notsell[n – 1]). **Below is a calculation matrix for [1, 2, 3, 0, 2].

check my code on github: link