309. Best Time to Buy and Sell Stock with Cooldown

309. 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:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

My Solutions:

和714类似，因为交易之间必须空出一天，对于每一天，有三种动作，buy, sell, cooldown。sell 和 cooldown 可以合并成一种状态，因为手里最终没有股票。最终需要的结果是 sell，即手里股票卖了获得最大利润。用两个数组来记录当前持股和未持股的状态

sells[i]表示在第i天不持有股票所能获得的最大累计收益
buys[i]表示在第i天持有股票所能获得的最大累计收益

初始化数组：
sells[0] = 0
buys[0] = -prices[0]
buys[1] = max(-prices[0], -prices[1]) 第1天有股票，只可能是第0天或者第1天买入的

对于sell[i]，最大利润有两种可能，当天是否将这只股票卖掉取决于卖掉能否获得更大的利润 （这部分和#714一样，除了714买股票需要手续费）

1. 今天跟昨天未持股状态一样

2. 今天卖了股票

sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}

对于buy[i]，最大利润有两种可能，当天是否买取决于买了之后是否比之前买所剩余的利润大。

1. 今天跟昨天持股状态一样

2. 前天卖了股票，今天买了股票，因为 cooldown 只能隔天交易，所以今天买股票要追溯到前天的状态。（这部分在这一题是sell[i-2]，#714不需要cooldown，所以是sell[i-1]）

buy[i] = max{buy[i-1], sell[i-2] - prices[i]}

状态转移方程：

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

最终要求的结果是sell[n - 1]，表示最后一天结束时，手里没有股票时的最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        
        int n = prices.length; 
        if (n <= 1) return 0; 
        int[] buy = new int[n];
        int[] sell = new int[n];
        
        buy[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            if (i == 1) buy[1] = Math.max(-prices[0], -prices[1]);
            else buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);

            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[n - 1]; 
    }
}

这个算法的空间复杂度是O(n)，不过由于sell[i]依赖前一项，buy[i]依赖前两项，所以可以优化到O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int sell = 0, preSell = 0, buy = Integer.MIN_VALUE, preBuy = 0;
        for (int p : prices) {
            preBuy = buy;
            buy = Math.max(preBuy, preSell - p);
            preSell = sell;
            sell = Math.max(preSell, preBuy + p);
        }
        return sell;
    }
    
    // 也可以这样写
    int sell = 0, preSell = 0, buy = -prices[0];    
    for (int i = 1; i < prices.length; i++) {
        int temp = sell;
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, (i > 1 ? preSell : 0) - prices[i]);
        preSell = temp;
    }
    return sell;
}