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)
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
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.
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