Description
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
Constraints:
1 <= prices.length <= 50000 <= prices[i] <= 1000
Solutions
Solution 1: Memoization Search
We design a function dfs(i, j), which represents the maximum profit that can be obtained starting from the ith day with state j. The values of j are 0 and 1, respectively representing currently not holding a stock and holding a stock. The answer is dfs(0, 0).
The execution logic of the function dfs(i, j) is as follows:
If i ≥ n, it means that there are no more stocks to trade, so return 0;
Otherwise, we can choose not to trade, then dfs(i, j) = dfs(i + 1, j). We can also trade stocks. If j > 0, it means that we currently hold a stock and can sell it, then dfs(i, j) = prices[i] + dfs(i + 2, 0). If j = 0, it means that we currently do not hold a stock and can buy, then dfs(i, j) = -prices[i] + dfs(i + 1, 1). Take the maximum value as the return value of the function dfs(i, j).
The answer is dfs(0, 0).
To avoid repeated calculations, we use the method of memoization search, and use an array f to record the return value of dfs(i, j). If f[i][j] is not -1, it means that it has been calculated, and we can directly return f[i][j].
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array prices.
PythonJavaC++GoTypeScript
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j)
if j:
ans = max(ans, prices[i] + dfs(i + 2, 0))
else:
ans = max(ans, -prices[i] + dfs(i + 1, 1))
return ans
return dfs(0, 0)(code-box)
class Solution {
private int[] prices;
private Integer[][] f;
public int maxProfit(int[] prices) {
this.prices = prices;
f = new Integer[prices.length][2];
return dfs(0, 0);
}
private int dfs(int i, int j) {
if (i >= prices.length) {
return 0;
}
if (f[i][j] != null) {
return f[i][j];
}
int ans = dfs(i + 1, j);
if (j > 0) {
ans = Math.max(ans, prices[i] + dfs(i + 2, 0));
} else {
ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
}
return f[i][j] = ans;
}
}(code-box)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f[n][2];
memset(f, -1, sizeof(f));
function<int(int, int)> dfs = [&](int i, int j) {
if (i >= n) {
return 0;
}
if (f[i][j] != -1) {
return f[i][j];
}
int ans = dfs(i + 1, j);
if (j) {
ans = max(ans, prices[i] + dfs(i + 2, 0));
} else {
ans = max(ans, -prices[i] + dfs(i + 1, 1));
}
return f[i][j] = ans;
};
return dfs(0, 0);
}
};(code-box)
func maxProfit(prices []int) int {
n := len(prices)
f := make([][2]int, n)
for i := range f {
f[i] = [2]int{-1, -1}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= n {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := dfs(i+1, j)
if j > 0 {
ans = max(ans, prices[i]+dfs(i+2, 0))
} else {
ans = max(ans, -prices[i]+dfs(i+1, 1))
}
f[i][j] = ans
return ans
}
return dfs(0, 0)
}(code-box)
function maxProfit(prices: number[]): number {
const n = prices.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 2 }, () => -1));
const dfs = (i: number, j: number): number => {
if (i >= n) {
return 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
let ans = dfs(i + 1, j);
if (j) {
ans = Math.max(ans, prices[i] + dfs(i + 2, 0));
} else {
ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
}
return (f[i][j] = ans);
};
return dfs(0, 0);
}(code-box)
Solution 2: Dynamic Programming
We can also use dynamic programming to solve this problem.
We define f[i][j] to represent the maximum profit that can be obtained on the ith day with state j. The values of j are 0 and 1, respectively representing currently not holding a stock and holding a stock. Initially, f[0][0] = 0, f[0][1] = -prices[0].
When i ≥ 1, if we currently do not hold a stock, then f[i][0] can be obtained by transitioning from f[i - 1][0] and f[i - 1][1] + prices[i], i.e., f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]). If we currently hold a stock, then f[i][1] can be obtained by transitioning from f[i - 1][1] and f[i - 2][0] - prices[i], i.e., f[i][1] = max(f[i - 1][1], f[i - 2][0] - prices[i]). The final answer is f[n - 1][0].
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array prices.
We notice that the transition of state f[i][] is only related to f[i - 1][] and f[i - 2][0], so we can use three variables f, f_0, f_1 to replace the array f, optimizing the space complexity to O(1).
PythonJavaC++GoTypeScript
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
f = [[0] * 2 for _ in range(n)]
f[0][1] = -prices[0]
for i in range(1, n):
f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i])
f[i][1] = max(f[i - 1][1], f[i - 2][0] - prices[i])
return f[n - 1][0](code-box)
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] f = new int[n][2];
f[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
f[i][1] = Math.max(f[i - 1][1], (i > 1 ? f[i - 2][0] : 0) - prices[i]);
}
return f[n - 1][0];
}
}(code-box)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f[n][2];
memset(f, 0, sizeof(f));
f[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]);
f[i][1] = max(f[i - 1][1], (i > 1 ? f[i - 2][0] : 0) - prices[i]);
}
return f[n - 1][0];
}
};(code-box)
func maxProfit(prices []int) int {
n := len(prices)
f := make([][2]int, n)
f[0][1] = -prices[0]
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1]+prices[i])
if i > 1 {
f[i][1] = max(f[i-1][1], f[i-2][0]-prices[i])
} else {
f[i][1] = max(f[i-1][1], -prices[i])
}
}
return f[n-1][0]
}(code-box)
function maxProfit(prices: number[]): number {
const n = prices.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 2 }, () => 0));
f[0][1] = -prices[0];
for (let i = 1; i < n; ++i) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
f[i][1] = Math.max(f[i - 1][1], (i > 1 ? f[i - 2][0] : 0) - prices[i]);
}
return f[n - 1][0];
}(code-box)
Solution 3
PythonJavaC++GoTypeScript
class Solution:
def maxProfit(self, prices: List[int]) -> int:
f, f0, f1 = 0, 0, -prices[0]
for x in prices[1:]:
f, f0, f1 = f0, max(f0, f1 + x), max(f1, f - x)
return f0(code-box)
class Solution {
public int maxProfit(int[] prices) {
int f = 0, f0 = 0, f1 = -prices[0];
for (int i = 1; i < prices.length; ++i) {
int g0 = Math.max(f0, f1 + prices[i]);
f1 = Math.max(f1, f - prices[i]);
f = f0;
f0 = g0;
}
return f0;
}
}(code-box)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int f = 0, f0 = 0, f1 = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
int g0 = max(f0, f1 + prices[i]);
f1 = max(f1, f - prices[i]);
f = f0;
f0 = g0;
}
return f0;
}
};(code-box)
func maxProfit(prices []int) int {
f, f0, f1 := 0, 0, -prices[0]
for _, x := range prices[1:] {
f, f0, f1 = f0, max(f0, f1+x), max(f1, f-x)
}
return f0
}(code-box)
function maxProfit(prices: number[]): number {
let [f, f0, f1] = [0, 0, -prices[0]];
for (const x of prices.slice(1)) {
[f, f0, f1] = [f0, Math.max(f0, f1 + x), Math.max(f1, f - x)];
}
return f0;
}(code-box)
