Best Time to Buy and Sell Stock with Cooldown(Medium)

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)

例子：

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

maxProfit = 3

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

解题思路：

这个问题的状态由3个交易操作组成：buy,sell,reset，reset表示当天没有交易（一天的冷却（CD）时间）。

交易序列可以由buy,sell,reset任意一个结束。我们用buy,sell,reset操作构成的数组表示一个交易序列：

buy[i]表示在第i天之前,交易序列的最后一个操作是buy，此时的最大收益。
sell[i]表示在第i天之前,交易序列的最后一个操作是sell，此时的最大收益。
rest[i]表示在第i天之前,交易序列的最后一个操作是reset，此时的最大收益。

按照上述定义，可以得到交易函数的递推式为（price表示第i天的股票价格）：

buy[i] = max(rest[i-1]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

根据股票交易规则，我们可以得到下面的结论：buy[i] <= rest[i] <= sell[i]，结合下面两个方程式：

buy[i] <= rest[i] <= sell[i]
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

可以得到：rest[i] = sell[i-1]

这样，我们可以将上面三个递推式精简到两个：

buy[i] = max(sell[i-2]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])

还可以做进一步优化，由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法，参见代码如下：

public int maxProfit(int[] prices) {
    int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
    for (int price : prices) {
        prev_buy = buy;
        buy = Math.max(prev_sell - price, prev_buy);
        prev_sell = sell;
        sell = Math.max(prev_buy + price, prev_sell);
    }
    return sell;
}

References:

1 本题思路解析

Best Time to Buy and Sell Stock with Cooldown