Best Time to Buy and Sell Stock with Cooldown

119.8k
0

An integer array prices is given, where prices[index] represents the stock price on day index.

Any number of transactions may be completed. Every transaction contains one purchase followed by one sale, and only one stock may be held at a time. A sale blocks another purchase on the next day. Return the maximum total profit.

Example 1

Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: Buying at 1, selling at 2, resting for one day, buying at 0, and selling at 2 produces profit 1 + 2 = 3.

Example 2

Input: prices = [5]
Output: 0
Explanation: A single price cannot complete a purchase and sale, so skipping trading keeps profit 0.

Recursion

Each day offers a small choice. An empty portfolio can buy at the current price or wait. A portfolio holding one stock can sell at the current price or keep holding. A sale moves the next decision two days ahead, naturally reserving the skipped day for cooldown.

State solve(index, canBuy) stores the best profit from day index onward. Flag canBuy records stock ownership. Initial state (0, 1) begins on day 0 with an empty portfolio, so every legal trading sequence remains available.

Algorithm

  • Begin with state (0, 1) because trading starts on the first day with no stock held.

  • Stop with profit 0 after the price array ends because no later transaction can add revenue.

  • Explore a purchase and a skipped day when canBuy = 1, subtracting the current price only for the purchase branch because buying spends money.

  • Explore a sale and a holding day when canBuy = 0, adding the current price only for the sale branch because selling realizes revenue.

  • Move the sale branch to index + 2 because the next day must remain unavailable for a new purchase.

  • Keep the larger legal branch result at every state because an optional action must never reduce the best available profit.

  • Return the result for (0, 1) because the starting state represents the complete price sequence and an empty portfolio.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best profit from one trading state.
int solve(
int index,
int canBuy,
vector<int>& prices
) {
int n = prices.size();
// No trading day remains after the array ends.
if (index >= n) {
return 0;
}
// An empty portfolio allows buying or waiting.
if (canBuy == 1) {
// Buying spends today's price and opens a position.
int buy = -prices[index] + solve(
index + 1, 0, prices
);
// Waiting preserves an empty portfolio.
int skip = solve(index + 1, 1, prices);
// The better empty-portfolio choice is kept.
return max(buy, skip);
}
// Selling earns money and forces one rest day.
int sell = prices[index] + solve(
index + 2, 1, prices
);
// Holding keeps the stock for a later sale.
int hold = solve(index + 1, 0, prices);
// The better held-stock choice is kept.
return max(sell, hold);
}
public:
// Returns the largest profit with one-day cooldowns.
int maxProfit(vector<int>& prices) {
// Trading starts empty on the first day.
return solve(0, 1, prices);
}
};
// Driver code
int main() {
vector<int> prices = {1, 2, 3, 0, 2};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of days, because each state can create two recursive branches across a maximum decision depth of N days.

Space Complexity: O(N), because the recursion stack can contain at most one active call for each day.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion reaches the same combination of day and ownership state through different trading histories. Recomputing an identical state adds work without changing the best future profit.

A two-dimensional array named dp stores every calculated state. Each recursive choice remains unchanged, including the two-day jump after a sale. A cached value returns immediately on later visits, so only repeated work disappears.

Algorithm

  • Create dp[index][canBuy] with sentinel value -1 so every uncalculated trading state has a clear marker.

  • Start from (0, 1) because no stock is held before the first day and every transaction remains available.

  • Stop after the price array ends because an exhausted suffix cannot produce additional profit.

  • Return a stored dp value before branching because identical states never depend on the earlier trading path.

  • Evaluate buy-or-wait choices for an empty portfolio and sell-or-hold choices for an open position because either legal action can produce the best profit.

  • Move two days ahead only after selling because the skipped index represents the compulsory cooldown day.

  • Store the larger legal choice in dp because later visits can reuse the best result, then return the starting state's cached value.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns a cached profit for one trading state.
int solve(
int index,
int canBuy,
vector<int>& prices,
vector<vector<int>>& dp
) {
int n = prices.size();
// No trading day remains after the array ends.
if (index >= n) {
return 0;
}
// A calculated state can be reused without branching.
if (dp[index][canBuy] != -1) {
return dp[index][canBuy];
}
// An empty portfolio allows buying or waiting.
if (canBuy == 1) {
// Buying spends today's price and opens a position.
int buy = -prices[index] + solve(
index + 1, 0, prices, dp
);
// Waiting preserves an empty portfolio.
int skip = solve(index + 1, 1, prices, dp);
// Cache storage prevents later recalculation.
dp[index][canBuy] = max(buy, skip);
return dp[index][canBuy];
}
// Selling earns money and forces one rest day.
int sell = prices[index] + solve(
index + 2, 1, prices, dp
);
// Holding keeps the stock for a later sale.
int hold = solve(index + 1, 0, prices, dp);
// Cache storage prevents later recalculation.
dp[index][canBuy] = max(sell, hold);
return dp[index][canBuy];
}
public:
// Returns the largest profit with cached states.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// Sentinel values mark every state as uncalculated.
vector<vector<int>> dp(
n, vector<int>(2, -1)
);
// Trading starts empty on the first day.
return solve(0, 1, prices, dp);
}
};
// Driver code
int main() {
vector<int> prices = {1, 2, 3, 0, 2};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because there are 2 × N reachable day-and-ownership states, and each state performs constant transition work once.

Space Complexity: O(N), because the dp array stores 2 × N values, while the recursion stack can reach a depth of N.

Tabulation

Memoization already proves day and ownership status fully define a state. Tabulation calculates the same states in reverse day order, so every next-day and post-cooldown answer exists before an earlier day needs the value.

Array dp receives two extra rows. Row n handles a normal move beyond the last day, while row n + 1 handles the two-day jump after a sale on the final day. Both rows contain zero because no future trade remains.

Algorithm

  • Create a zero-filled dp table with n + 2 rows and two ownership states because a sale transition may read day index + 2.

  • Keep rows n and n + 1 at zero because both rows represent exhausted price ranges with no remaining profit.

  • Process days from right to left so every next-day and two-days-ahead state is ready before the current transition.

  • Calculate dp[index][1] from buying or waiting because an empty portfolio permits exactly the two choices.

  • Calculate dp[index][0] from selling or holding, reading dp[index + 2][1] for a sale because the skipped row enforces cooldown.

  • Store the larger result for each ownership state because the best suffix decision must remain available to earlier days.

  • Return dp[0][1] because day 0 begins with an empty portfolio and permission to buy.

Dry Run

best-time-to-buy-and-sell-stock-with-cooldown-tabulation.png

best-time-to-buy-and-sell-stock-with-cooldown-tabulation.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the largest profit with bottom-up states.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// Extra rows support both future-day transitions.
vector<vector<int>> dp(
n + 2, vector<int>(2, 0)
);
// Backward order keeps future answers ready.
for (int index = n - 1; index >= 0; index--) {
// Buying spends money before a later sale.
int buy = -prices[index] + dp[index + 1][0];
// Waiting preserves an empty portfolio.
int skip = dp[index + 1][1];
// The best empty-portfolio state is stored.
dp[index][1] = max(buy, skip);
// Selling earns money and skips one buying day.
int sell = prices[index] + dp[index + 2][1];
// Holding preserves the open position.
int hold = dp[index + 1][0];
// The best held-stock state is stored.
dp[index][0] = max(sell, hold);
}
// The empty starting state contains the answer.
return dp[0][1];
}
};
// Driver code
int main() {
vector<int> prices = {1, 2, 3, 0, 2};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because each day computes two ownership states with constant transition work.

Space Complexity: O(N), because the dp table stores two values for each of the N days, along with two constant-sized base rows.

Space Optimization

Tabulation reads only rows index + 1 and index + 2 while building the current row. Every other table row has already served the required transitions, so retaining the full history adds no value.

Arrays nextOne and nextTwo preserve the two future rows. Array current calculates both present ownership states before any shift occurs. Moving nextOne into nextTwo first and current into nextOne second preserves the correct day meanings for the next iteration.

Algorithm

  • Keep two zero-filled state arrays named nextOne and nextTwo because the current day reads only one and two days ahead.

  • Process prices from right to left so both retained future arrays already represent completed suffix calculations.

  • Calculate the current empty-portfolio state from buying or waiting because both choices depend only on nextOne.

  • Calculate the current held-stock state from selling or holding, using nextTwo after a sale to preserve the cooldown day.

  • Store both results in a fresh current array because overwriting a future array early would mix different day meanings.

  • Shift nextOne into nextTwo before moving current into nextOne because the preceding day needs both present future layers.

  • Return nextOne[1] after the final shift because the retained row represents day 0 with permission to buy.

Dry Run

Time to buy and sell stock cooldown Space Optimization

Time to buy and sell stock cooldown Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the largest profit with rolling states.
int maxProfit(vector<int>& prices) {
int n = prices.size();
// NextOne stores states one day ahead.
vector<int> nextOne(2, 0);
// NextTwo stores states two days ahead.
vector<int> nextTwo(2, 0);
// Backward order keeps both future layers ready.
for (int index = n - 1; index >= 0; index--) {
// Current receives both present-day states.
vector<int> current(2, 0);
// Buying or waiting forms the empty state.
int buy = -prices[index] + nextOne[0];
int skip = nextOne[1];
current[1] = max(buy, skip);
// Selling or holding forms the owned state.
int sell = prices[index] + nextTwo[1];
int hold = nextOne[0];
current[0] = max(sell, hold);
// Shifts preserve one-day and two-day meanings.
nextTwo = nextOne;
nextOne = current;
}
// The empty starting state contains the answer.
return nextOne[1];
}
};
// Driver code
int main() {
vector<int> prices = {1, 2, 3, 0, 2};
Solution obj;
cout << obj.maxProfit(prices);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because each day computes two rolling ownership states with constant work.

Space Complexity: O(1), because three fixed-size arrays of two values retain only the current and required future states.

Interview follow-up Questions

No. The cooldown lasts for the entire day after the sale, so the two-day gap includes the selling day and the cooldown day. Therefore, if you sell on Day i, the next purchase can only happen on Day i + 2.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Print Longest Increasing Subsequence

Given an integer array arr , find one longest subsequence with values appearing in strictly increasing order. A subsequence keeps the original relative order but may skip any number of elements. Re...

115.1k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

Input: prices = [1, 3, 2, 8, 4, 9] , fee = 2 Output: 8 Explanation: Buying at 1 and selling at 8 earns 8 - 1 - 2 = 5 . Buying at 4 and selling at 9 earns 9 - 4 - 2 = 3 . The maximum total profit is...

65.7k
Comments0