309 Best Time to Buy and Sell Stock with Cooldown

309. Best Time to Buy and Sell Stock with Cooldown

1. Question

Say you have an array for which theithelement is the price of a given stock on dayi.

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]

2. Implementation

(1) DP:

buy[i]表示在第i天我们买股票所获得的最大利润, buy[i]的状态取决于两方面:

1.不买任何股票，和前一天一样

2.买第i天股票，但因为有cool down，所以第i天买股票必须要i - 2天前卖了股票后

所以状态转移方程为 buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i])

sell[i]表示在第i天我们卖股票所获得的最大利润, 和buy[i]类似，sell[i]的状态取决于两方面:

1.不卖任何股票，和前一天一样

1. 卖第i天股票，注意这里卖股票没有cooldown的限制，即前天买了股票后第二天可以卖

状态转移方程为 sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i])

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];

        // Initialization
        buy[0] = -prices[0];
        sell[0] = 0;

        for (int i = 1; i < n; i++) {
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = Math.max(buy[i - 1], (i > 1 ? sell[i - 2] : 0) - prices[i]);
        }

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

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)