LeetCode Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the i^th 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]

---

又是股票买卖问题。在LeetCode Best Time to Buy and Sell Stock II的基础上，限制一次交易之后必须冷却一天，隔天才能再次买入。此时就不能再用贪心策略了，还需要用DP。参考这篇博客解法I。 定义两个数组sells和buys，sells[i]表示第i天的动作是卖出，截止当前的最大收益；buys[i]表示第i天的动作是买入，截止当前的最大收益。显然buys[0]=–prices[0], sells[0]=0。 令profit=prices[i]-prices[i-1]，递推公式如下：

1. sells[i]=max(buys[i-1]+prices[i], sells[i-1]+profit)
2. buys[i]=max(sells[i-2]-prices[i], buys[i-1]-profit)

含义为：

1. 第i天卖出的收益=max(第i-1天买入+第i天卖出的收益，第i-1天卖出~但反悔了~改为第i天卖出)
2. 第i天买入的收益=max(第i-2天卖出~第i-1天冷却~第i天买入的负收益，第i-1天买入~但反悔了~改为第i天买入)

而事实上：

1. 第i-1天卖出后反悔，改为第i天卖出 等价于 第i-1天持有股票，第i天再卖出
2. 第i-1天买入后反悔，改为第i天买入 等价于 第i-1天没有股票，第i天再买入

所求的最大收益为max(sells)。显然，卖出股票时才可能获得收益。完整代码如下： [cpp] class Solution { public: int maxProfit(vector<int>& prices) { int days = prices.size(); if (days < 2)return 0; vector<int> sells(days), buys(days); buys[0] = -prices[0]; int ans = 0; for (int i = 1; i < days; ++i) { int profit = prices[i] – prices[i – 1]; sells[i] = max(buys[i – 1] + prices[i], sells[i – 1] + profit); buys[i] = max(i > 1 ? sells[i – 2] – prices[i] : INT_MIN, buys[i – 1] – profit); ans = max(ans, sells[i]); } return ans; } }; [/cpp] 本代码提交AC，用时6MS。]]>