Dare2Solve
You are given an array prices
where prices[i]
is the price of a stock on the ith day. You can decide each day whether to buy, sell, or skip. However, after you sell a stock, you cannot buy again the next day due to a cooldown period of 1 day. Your task is to find the maximum profit you can achieve. You can hold at most one share of stock at a time.
The key idea is to use dynamic programming to track the maximum profit at each day based on two possible states:
If you are holding a stock, you can either sell it and enter a cooldown period, or hold it until a future date. If you are not holding a stock, you can either buy a stock or skip the day. The cooldown period prevents consecutive buying and selling, which creates dependencies between days. This makes the problem well-suited for dynamic programming.
State Definition:
dpb[i]
: Maximum profit if you buy/hold stock on the ith day.dps[i]
: Maximum profit if you sell stock on the ith day.Recursive Transition:
i
and move to the next day holding the stock. The cost would be subtracted from your profit.i
and check the maximum profit for day i+1
.i
, add the profit from selling, and move to day i+2
(due to the cooldown).i
and move to the next day.Base Case:
Memoization:
dpb
and dps
to store intermediate results, preventing recalculations of the same subproblem.Final Answer:
dpb[0]
, representing the maximum profit you can make starting from day 0.prices
array. This is because each day is processed once, and for each day, we decide whether to buy, sell, or skip, with all operations taking constant time.prices
array. This is due to the dpb
and dps
arrays, which store results for each day.class Solution {
public:
int maxProfit(std::vector<int>& prices) {
int n = prices.size();
std::vector<int> dpb(n, 0), dps(n, 0);
std::function<int(int, int)> dfs = [&](int i, int stockPrice) -> int {
if (i >= n)
return 0;
if (stockPrice == -1 && dpb[i])
return dpb[i];
if (stockPrice != -1 && dps[i])
return dps[i];
int price = prices[i];
int skip = dfs(i + 1, stockPrice);
if (stockPrice != -1) {
int sell = price + dfs(i + 2, -1);
dps[i] = std::max(skip, sell);
return dps[i];
} else {
int buy = dfs(i + 1, price) - price;
dpb[i] = std::max(buy, skip);
return dpb[i];
}
};
dfs(0, -1);
return dpb[0];
}
};
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dpb = [0] * n
dps = [0] * n
def dfs(i, stockPrice):
if i >= n:
return 0
if stockPrice is None and dpb[i]:
return dpb[i]
if stockPrice is not None and dps[i]:
return dps[i]
price = prices[i]
skip = dfs(i + 1, stockPrice)
if stockPrice is not None:
sell = price + dfs(i + 2, None)
dps[i] = max(skip, sell)
return dps[i]
else:
buy = dfs(i + 1, price) - price
dpb[i] = max(buy, skip)
return dpb[i]
dfs(0, None)
return dpb[0]
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[] dpb = new int[n]; // dp for buy state
int[] dps = new int[n]; // dp for sell state
Arrays.fill(dpb, -1); // Initialize with -1 (unvisited)
Arrays.fill(dps, -1); // Initialize with -1 (unvisited)
return dfs(prices, dpb, dps, 0, null);
}
private int dfs(int[] prices, int[] dpb, int[] dps, int i, Integer stockPrice) {
if (i >= prices.length) {
return 0;
}
if (stockPrice == null && dpb[i] != -1) { // If we haven't bought a stock yet
return dpb[i];
}
if (stockPrice != null && dps[i] != -1) { // If we have already bought a stock
return dps[i];
}
int price = prices[i];
int skip = dfs(prices, dpb, dps, i + 1, stockPrice); // Skip this day
if (stockPrice != null) { // If holding a stock, we can sell
int sell = price + dfs(prices, dpb, dps, i + 2, null); // Sell and go to i + 2 because of cooldown
dps[i] = Math.max(skip, sell);
return dps[i];
} else { // If not holding a stock, we can buy
int buy = dfs(prices, dpb, dps, i + 1, price) - price; // Buy and hold stock
dpb[i] = Math.max(buy, skip);
return dpb[i];
}
}
}
var maxProfit = function(prices) {
let res = 0;
const dpb = [];
const dps = [];
function dfs(i, stockPrice) {
if (i >= prices.length) {
return 0;
}
if (stockPrice === undefined && dpb[i]) {
return dpb[i];
}
if (stockPrice !== undefined && dps[i]) {
return dps[i];
}
const price = prices[i];
const skip = dfs(i + 1, stockPrice);
if (stockPrice !== undefined) {
// let newProfit += price;
const sell = price + dfs(i + 2, undefined);
dps[i] = Math.max(skip, sell);
return dps[i];
} else {
const buy = dfs(i + 1, price) - price;
dpb[i] = Math.max(buy, skip);
return dpb[i];
}
}
dfs(0, undefined);
return dpb[0];
};