309. Best Time to Buy and Sell Stock with Cooldown (Medium)
https://leetcode.com/problems/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]
Solutions
class Solution {
// FIXME This problem is not easy to understand.
public int maxProfit(int[] prices) {
if (prices.length == 0 || prices.length == 1) {
return 0;
}
int[] maxProfit = new int[prices.length];
maxProfit[0] = 0;
maxProfit[1] = Math.max(0, prices[1] - prices[0]);
// profit can be calculated by sellPrice - buyPrice
// variable value represents the best buy price, it should be the smaller one.
int value = Math.max(-prices[0], -prices[1]);
for (int i = 2; i < prices.length; i++) {
// if sell on ith day, tmp is the floating profit
int tmp = prices[i] + value;
// no need to sell
if (tmp <= maxProfit[i - 1]) {
maxProfit[i] = maxProfit[i - 1];
}
// sell it on ith day because profit increases
else {
maxProfit[i] = tmp;
}
// but if the profit of the (i-1)th day is larger than sell it today, sell it on (i-1)th
// day, then buy it today.
if (maxProfit[i - 2] > tmp) {
value = maxProfit[i - 2] - prices[i];
}
}
return maxProfit[prices.length - 1];
}
}
Incorrect Solutions
class Solution {
// Another Dynamic Programming problem.
Map<String, Integer> maxx = new HashMap<>();
public int maxProfit(int[] prices) {
return recurse(prices, 0, true, -1);
}
private int recurse(int[] prices, int day, boolean canBuy, int strikePrice) {
/*
// if strike price -1, no stock bought or all sold.
if (strikePrice != -1) {
canBuy = false;
}
// no stock bought and last time just sold
else if (!canBuy) {
canBuy = true;
}
// else canBuy = true, keep the original value
*/
if (day == prices.length) {
// even with condition strikePrice > 0 which means you have unsold stocks, return 0.
return 0;
}
String key = day + "#" + strikePrice + "#" + canBuy;
if (maxx.containsKey(key)) {
return maxx.get(key);
}
// You are allowed to buy
if (canBuy) {
// 1. buy it
int rst1 = recurse(prices, day + 1, false, prices[day]);
// 2. do not buy it
int rst2 = recurse(prices, day + 1, true, -1);
maxx.put(key, Math.max(rst1, rst2));
}
// Not allowed to buy and you already bought
else if (strikePrice != -1){
// 1. sell it
int rst1 = recurse(prices, day + 1, false, -1) + prices[day] - strikePrice;
// 2. keep it
int rst2 = recurse(prices, day + 1, false, strikePrice);
maxx.put(key, Math.max(rst1, rst2));
}
// Not allowed to buy, just sold last yesterday
else {
int rst1 = recurse(prices, day + 1, true, strikePrice);
maxx.put(key, rst1);
}
return maxx.get(key);
}
}