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]

Tips:

• 基础： 要额外O(n)空间 有了cooldown之后需要设置buy和sell两个数组，buy[i]表示第i天的时候买入股份的最大利益，sell[i]表示第i天的时候卖出股份的最大利益。

初始化：

        buy[0] = -prices[0]; 
        buy[1] = prices[1] > prices[0] ? -prices[0] : -prices[1];
        sell[0] = 0; 
        sell[1] = prices[1] > prices[0] ? prices[1] - prices[0] : 0;

状态转移方程为：

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

上述方程的含义为：

第i天买入的最大累积收益 = max(第i-2天卖出，第i天买入；第i-1天买入，第i天持有) 第i天卖出的最大累积收益 = max(第i-1天买入~第i天卖出的最大累积收益；第i-1天卖出，第i天没交易)

• 优化： 只需要额外O(1)空间。

如果不满足于空间复杂度，可进行优化，用prev_sell和prev_buy优化，因为sell和buy只与他们的前两天有关。

Code：

基础：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        if (prices.length == 1) {
            return 0;
        }
        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        buy[0] = -prices[0]; 
        buy[1] = prices[1] > prices[0] ? -prices[0] : -prices[1];
        sell[0] = 0; 
        sell[1] = prices[1] > prices[0] ? prices[1] - prices[0] : 0;
        for (int i = 2; i < n; i++) {
            buy[i] = Math.max(sell[i - 2] - prices[i], buy[i - 1]);
            sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
        }
        return sell[n - 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;
}