## Best Time to Buy and Sell Stock with Cooldown

### 描述

Almost the ame as Best Time to Buy and Sell Stock II but with one restriction: 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


### 分析

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

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

### 代码1 O(n)空间

// Best Time to Buy and Sell Stock with Cooldown
// Time Complexity: O(n), Space Complexity: O(n)
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;

int[] sell = new int[prices.length];
sell[0] = 0;

for (int i = 1; i < prices.length; ++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 sell[prices.length - 1];
}
}

### 代码2 O(1)空间

// Best Time to Buy and Sell Stock with Cooldown
// Time Complexity: O(n), Space Complexity: O(1)
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;

int curSell = 0;   // sell[i]
int prevSell = 0;  // sell[i-2]

for (int i = 1; i < prices.length; ++i) {
final int tmp = curSell;
curSell = Math.max(curSell, buy + prices[i]);
buy = Math.max(buy, (i > 1 ? prevSell : 0) - prices[i]);
prevSell = tmp;
}
return curSell;
}
}