
Description
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.
Intuition
The key idea is to use dynamic programming to track the maximum profit at each day based on two possible states:
- When you are holding a stock.
- When you are not holding a stock.
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.
Approach
- State Definition:
- Define two arrays:
-
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:
- If you are not holding a stock, you can:
- Buy stock on day
i
and move to the next day holding the stock. The cost would be subtracted from your profit. - Skip buying on dayi
and check the maximum profit for dayi+1
. - If you are holding a stock, you can: - Sell the stock on dayi
, add the profit from selling, and move to dayi+2
(due to the cooldown). - Skip selling on dayi
and move to the next day. - Base Case: - If you exceed the length of the price array, the profit is zero because no more transactions can be made.
- Memoization:
- Use two arrays
dpb
anddps
to store intermediate results, preventing recalculations of the same subproblem. - Final Answer:
- The result will be in
dpb[0]
, representing the maximum profit you can make starting from day 0.
Complexity
Time Complexity:
- The time complexity is (O(n)), where (n) is the length of the
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.
Space Complexity:
- The space complexity is (O(n)), where (n) is the length of the
prices
array. This is due to thedpb
anddps
arrays, which store results for each day.
Code
C++
class Solution {
public:
int maxProfit(std::vector& prices) {
int n = prices.size();
std::vector dpb(n, 0), dps(n, 0);
std::function 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];
}
};
Python
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]
Java
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];
}
}
}
JavaScript
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];
};