Welcome to Subscribe On Youtube
309. Best Time to Buy and Sell Stock with Cooldown
Description
You are given an array prices
where prices[i]
is the price of a given stock on the i^{th}
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 <= 5000
0 <= 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 $i$th 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 \geq 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$.
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 $i$th 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 \geq 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)$.
Solution 3: Greedy
 The solution uses dynamic programming to keep track of the profit at each step. It defines three states for each day:
f1
represents the maximum profit achievable on dayi
if you own a stock. This means you’ve bought a stock and haven’t sold it yet.f2
represents the maximum profit achievable on dayi
if you’re in a cooldown period or have sold the stock and not bought another yet.f3
represents the maximum profit achievable on dayi
if you’re free to buy a stock, meaning you’ve neither bought a stock nor are in a cooldown period.
 The initial conditions are set as follows:
f1
is initialized toprices[0]
because buying a stock costs money, which is considered a negative profit on day 0.f2
andf3
are initialized to0
because you haven’t made any transactions yet.
 The for loop iterates over the prices starting from the second day (
prices[1:]
), and for each day, it calculates: The new
f1
as the maximum of staying in the currentf1
state or moving from thef3
state to thef1
state by buying a stock (pf3  price
). This decision reflects either holding onto the stock bought earlier or buying a new stock after a cooldown.  The new
f2
as the maximum of staying in the currentf2
state or moving from thef1
state to thef2
state by selling a stock (pf1 + price
). This captures the profit from selling a stock you own.  The new
f3
as the maximum of staying in the currentf3
state or moving from thef2
state to thef3
state (pf2
). This transition reflects the cooldown period after selling a stock before you can buy again.
 The new
 Finally, the function returns
f2
, which represents the maximum profit at the end of the trading period under the condition that you’ve sold your stock and possibly are in a cooldown period or not looking to buy immediately. Since you want to maximize profit, ending with an owned stock (f1
) is not considered for the final answer because you haven’t realized the profit from selling it. Ending in thef3
state doesn’t necessarily reflect the maximum profit, as it’s possible to have sold a stock on the last day, entering the cooldown with the profit included inf2
.

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; } }

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; } };

class Solution: def maxProfit(self, prices: List[int]) > int: f1, f2, f3 = prices[0], 0, 0 for price in prices[1:]: pf1, pf2, pf3 = f1, f2, f3 f1 = max(pf1, pf3  price) f2 = max(pf2, pf1 + price) f3 = max(pf3, pf2) # cooldown return f2 ############ 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 ############ class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) < 2: return 0 buy = [0] * len(prices) sell = [0] * len(prices) buy[0] = prices[0] buy[1] = max(prices[1], buy[0]) sell[0] = 0 sell[1] = max(prices[1]  prices[0], 0) for i in range(2, len(prices)): buy[i] = max(sell[i  2]  prices[i], buy[i  1]) sell[i] = max(prices[i] + buy[i  1], sell[i  1]) return max(sell)

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, fx) } return f0 }

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; }