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:
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] <= 1000Problem Overview: You are given an array prices where prices[i] is the stock price on day i. You can buy and sell multiple times, but after selling a stock you must wait one day before buying again (cooldown). The goal is to compute the maximum profit achievable under this constraint.
Approach 1: Recursive DP with Memoization (Time: O(n), Space: O(n))
Model the decision process day by day. At each index you track whether you are allowed to buy or you currently hold a stock. From a buy state, you either buy the stock and move to the sell state or skip the day. From a sell state, you either sell the stock and jump two days forward (due to the cooldown) or skip the day. A naive recursion explores many repeated states, so memoization stores results for each pair (day, holdingState). This converts the exponential search into linear time because each state is solved once. This approach clearly expresses the decision tree and is useful when first reasoning about the dynamic programming state transitions.
Approach 2: Iterative Dynamic Programming (State Machine) (Time: O(n), Space: O(1))
The optimal solution tracks three states while scanning the array once. hold represents the best profit while holding a stock, sold represents profit immediately after selling, and rest represents profit while in cooldown or doing nothing. For each price you update the states using transitions: buying moves from rest → hold, selling moves from hold → sold, and waiting moves from sold → rest. Because each state depends only on the previous day, you keep three variables instead of an entire DP table. The algorithm performs a single pass over the prices array, updating profits in constant time per element.
The key insight is separating "holding", "just sold", and "resting" states. The cooldown restriction is naturally enforced because buying is only allowed from the rest state, not from sold. This transforms the problem into a small deterministic state machine, a common pattern in dynamic programming problems involving stock trading constraints.
Recommended for interviews: The iterative dynamic programming state-machine approach. Interviewers expect an O(n) solution with constant space and clear state transitions. Starting with the recursive memoized version demonstrates understanding of the decision process, but converting it into the compact three-state DP shows strong optimization and problem modeling skills.
This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.
This C code defines a function maxProfit that takes the array of prices and its size. The dynamic programming state variables are initialized: hold representing the maximum profit holding a stock, sell for selling it, and cooldown for the situation with a cooldown period. It iterates through each price updating these states according to whether you sell, buy, or remain idle.
Time Complexity: O(n), where n is the number of days. Each day's prices are visited once.
Space Complexity: O(1), since only a fixed amount of extra space is used.
This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.
This C version uses a recursive function called solve that considers each day and whether you can buy or have to sell, using memoization for repetitive states. It attempts both buying and selling actions recursively and stores maximum profits attainable to avoid recomputation.
Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once.
Space Complexity: O(n), for the memoization table.
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 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.
Python
Java
C++
Go
TypeScript
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 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).
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the number of days. Each day's prices are visited once. |
| Recursive Approach with Memoization | Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once. |
| Memoization Search | — |
| Dynamic Programming | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n) | O(n) | When reasoning about decisions (buy, sell, skip) and building intuition for the DP states |
| Iterative Dynamic Programming (State Machine) | O(n) | O(1) | Optimal solution for interviews and production due to constant space and single pass |
Best Time to Buy and Sell Stock with Cooldown - Leetcode 309 - Python • NeetCode • 146,609 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock with Cooldown with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor