Stock Buy and Sell with Cooldown

Given an array arr[], where the ith element of arr[] represents the price of a stock on the ith day (all prices are non-negative integers). Find the maximum profit you can make by buying and selling stocks such that after selling a stock, you cannot buy again on the next day (i.e., there is a one-day cooldown).

Examples:

Input: arr[] = [0, 2, 1, 2, 3]
Output: 3
Explanation: You first buy on day 1, sell on day 2 then cool down, then buy on day 4, and sell on day 5. The total profit earned is (2-0) + (3-2) = 3, which is the maximum achievable profit.
Input: arr[] = [3, 1, 6, 1, 2, 4]
Output: 7
Explanation: You first buy on day 2 and sell on day 3 then cool down, then again you buy on day 5 and then sell on day 6. Clearly, the total profit earned is (6-1) + (4-2) = 7, which is the maximum achievable profit.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Recursion - O(2^n) Time and O(n) Space
[Better Approach 1] Using Top Down Dp (Memorization) - O(n) Time and O(n) Space
[Better Approach 2] Using Bottom Up Dp (Tabulation) - O(n) Time and O(n) Space
[Expected Approach] Using Space Optimization - O(n) Time and O(1) Space

[Naive Approach] Using Recursion - O(2ⁿ) Time and O(n) Space

The idea is to use recursion to explore all possible actions on each day — whether to buy, sell, or skip.

At any given day, we track whether we currently hold a stock using a variable buy:

buy == 0 → we don’t own a stock (we can buy).
buy == 1 → we already own a stock (we can sell).

For each day i, there are two possible actions:

If we can buy (buy == 0): We can either buy the stock (subtract its price from profit) or skip to the next day.
If we can sell (buy == 1): We can either sell the stock (add its price to profit and subtract the transaction fee k) or skip to the next day.

At each step, we take the maximum of these two choices. The recursion continues until we reach the end of the array, and the maximum profit obtained represents the final answer.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//Driver Code Ends


// Recursive Function to find profit
int findProfit(int i, int buy, vector<int>& arr) {
    int n = arr.size();

    // Base case
    if (i >= n) return 0;

    // If we can buy
    if (buy) {
        int take = -arr[i] + findProfit(i + 1, 0, arr);
        int skip = findProfit(i + 1, 1, arr);
        return max(take, skip);
    }

    // If we can sell
    else {
        int sell = arr[i] + findProfit(i + 2, 1, arr);
        int skip = findProfit(i + 1, 0, arr);
        return max(sell, skip);
    }
}

// Function to find maximum profit
int maxProfit(vector<int>& arr) {
    return findProfit(0, 1, arr);
}


//Driver Code Starts
int main() {
    vector<int> arr = {0, 2, 1, 2, 3};

    cout << maxProfit(arr);
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.Arrays;

class GFG {
//Driver Code Ends


    // Recursive function to find profit
    static int findProfit(int i, int buy, int[] arr) {
        int n = arr.length;

        // Base case
        if (i >= n) return 0;

        // If we can buy
        if (buy == 1) {
            int take = -arr[i] + findProfit(i + 1, 0, arr);
            int skip = findProfit(i + 1, 1, arr);
            return Math.max(take, skip);
        }

        // If we can sell
        else {
            int sell = arr[i] + findProfit(i + 2, 1, arr);
            int skip = findProfit(i + 1, 0, arr);
            return Math.max(sell, skip);
        }
    }

    // Function to find maximum profit
    static int maxProfit(int[] arr) {
        return findProfit(0, 1, arr);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {0, 2, 1, 2, 3};

        System.out.println(maxProfit(arr));
    }
}

//Driver Code Ends

Python

# Recursive function to find profit
def findProfit(i, buy, arr):
    n = len(arr)

    # Base case
    if i >= n:
        return 0

    # If we can buy
    if buy:
        take = -arr[i] + findProfit(i + 1, 0, arr)
        skip = findProfit(i + 1, 1, arr)
        return max(take, skip)

    # If we can sell
    else:
        sell = arr[i] + findProfit(i + 2, 1, arr)
        skip = findProfit(i + 1, 0, arr)
        return max(sell, skip)

# Function to find maximum profit
def maxProfit(arr):
    return findProfit(0, 1, arr)


if __name__ == "__main__":
#Driver Code Starts
    arr = [0, 2, 1, 2, 3]
    print(maxProfit(arr))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    // Recursive function to find profit
    static int findProfit(int i, int buy, int[] arr) {
        int n = arr.Length;

        // Base case
        if (i >= n) return 0;

        // If we can buy
        if (buy == 1) {
            int take = -arr[i] + findProfit(i + 1, 0, arr);
            int skip = findProfit(i + 1, 1, arr);
            return Math.Max(take, skip);
        }

        // If we can sell
        else {
            int sell = arr[i] + findProfit(i + 2, 1, arr);
            int skip = findProfit(i + 1, 0, arr);
            return Math.Max(sell, skip);
        }
    }

    // Function to find maximum profit
    static int maxProfit(int[] arr) {
        return findProfit(0, 1, arr);
    }


//Driver Code Starts
    public static void Main() {
        int[] arr = {0, 2, 1, 2, 3};

        Console.WriteLine(maxProfit(arr));
    }
}

//Driver Code Ends

JavaScript

// Recursive function to find profit
function findProfit(i, buy, arr) {
    const n = arr.length;

    // Base case
    if (i >= n) return 0;

    // If we can buy
    if (buy) {
        let take = -arr[i] + findProfit(i + 1, 0, arr);
        let skip = findProfit(i + 1, 1, arr);
        return Math.max(take, skip);
    }

    // If we can sell
    else {
        let sell = arr[i] + findProfit(i + 2, 1, arr);
        let skip = findProfit(i + 1, 0, arr);
        return Math.max(sell, skip);
    }
}

// Function to find maximum profit
function maxProfit(ar) {
    return findProfit(0, 1, arr);
}


// Driver code
//Driver Code Starts
let arr = [0, 2, 1, 2, 3];
console.log(maxProfit(arr));

//Driver Code Ends

Output

[Better Approach 1] Using Top Down Dp (Memorization) - O(n) Time and O(n) Space

The idea is to optimize the recursive solution by avoiding repeated calculations using memorization (top-down DP).

In the recursive approach, the same subproblems defined by the current index i (day number) and the state buy (whether we can buy or need to sell) are solved multiple times.

To handle this efficiently, we store the results of these subproblems in a 2D DP array dp[i][buy], where:

i represents the current day (0 to n-1), and
buy represents the action state (1 → can buy, 0 → can sell).

Whenever a subproblem is revisited, we directly return the stored value instead of recalculating it.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//Driver Code Ends


// Recursive function with memoization to find profit
int findProfit(int i, int buy, vector<int>& arr, vector<vector<int>>& dp) {
    int n = arr.size();

    // Base case
    if (i >= n) return 0;

    // If already computed
    if (dp[i][buy] != -1) return dp[i][buy];

    // If we can buy
    if (buy) {
        int take = -arr[i] + findProfit(i + 1, 0, arr, dp);
        int skip = findProfit(i + 1, 1, arr, dp);
        dp[i][buy] = max(take, skip);
    }

    // If we can sell
    else {
        int sell = arr[i] + findProfit(i + 2, 1, arr, dp);
        int skip = findProfit(i + 1, 0, arr, dp);
        dp[i][buy] = max(sell, skip);
    }

    return dp[i][buy];
}

// Function to find maximum profit
int maxProfit(vector<int>& arr) {
    int n = arr.size();
    
    vector<vector<int>> dp(n, vector<int>(2, -1));
    return findProfit(0, 1, arr, dp);
}


//Driver Code Starts
int main() {
    vector<int> arr = {0, 2, 1, 2, 3};

    cout << maxProfit(arr);
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.ArrayList;
import java.util.Arrays;

class GFG {
//Driver Code Ends


    // Recursive function with memoization to find profit
    static int findProfit(int i, int buy, int[] arr, int[][] dp) {
        int n = arr.length;
    
        // Base case
        if (i >= n) return 0;
    
        // If already computed
        if (dp[i][buy] != -1) return dp[i][buy];
    
        // If we can buy
        if (buy == 1) {
            int take = -arr[i] + findProfit(i + 1, 0, arr, dp);
            int skip = findProfit(i + 1, 1, arr, dp);
            dp[i][buy] = Math.max(take, skip);
        }
    
        // If we can sell
        else {
            int sell = arr[i] + findProfit(i + 2, 1, arr, dp);
            int skip = findProfit(i + 1, 0, arr, dp);
            dp[i][buy] = Math.max(sell, skip);
        }
    
        return dp[i][buy];
    }
    
    // Function to find maximum profit
    static int maxProfit(int[] arr) {
        int n = arr.length;    
    
        int[][] dp = new int[n][2];
        for (int[] row : dp) Arrays.fill(row, -1);
        return findProfit(0, 1, arr, dp);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {0, 2, 1, 2, 3};

        System.out.println(maxProfit(arr));
    }
}

//Driver Code Ends

Python

# Recursive function with memoization to find profit
def findProfit(i, buy, arr, dp):
    n = len(arr)

    # Base case
    if i >= n:
        return 0

    # If already computed
    if dp[i][buy] != -1:
        return dp[i][buy]

    # If we can buy
    if buy:
        take = -arr[i] + findProfit(i + 1, 0, arr, dp)
        skip = findProfit(i + 1, 1, arr, dp)
        dp[i][buy] = max(take, skip)
    else:
        sell = arr[i] + findProfit(i + 2, 1, arr, dp)
        skip = findProfit(i + 1, 0, arr, dp)
        dp[i][buy] = max(sell, skip)

    return dp[i][buy]

# Function to find maximum profit
def maxProfit(arr):
    n = len(arr)
    dp = [[-1 for _ in range(2)] for _ in range(n)]
    return findProfit(0, 1, arr, dp)


if __name__ == "__main__":
#Driver Code Starts
    arr = [0, 2, 1, 2, 3]

    print(maxProfit(arr))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    // Recursive function with memoization to find profit
    static int findProfit(int i, int buy, int[] arr, int[,] dp) {
        int n = arr.Length;

        // Base case
        if (i >= n) return 0;

        // If already computed
        if (dp[i, buy] != -1) return dp[i, buy];

        // If we can buy
        if (buy == 1) {
            int take = -arr[i] + findProfit(i + 1, 0, arr, dp);
            int skip = findProfit(i + 1, 1, arr, dp);
            dp[i, buy] = Math.Max(take, skip);
        }

        // If we can sell
        else {
            int sell = arr[i] + findProfit(i + 2, 1, arr, dp);
            int skip = findProfit(i + 1, 0, arr, dp);
            dp[i, buy] = Math.Max(sell, skip);
        }

        return dp[i, buy];
    }

    // Function to find maximum profit
    static int maxProfit(int[] arr) {
        int n =  arr.Length;
        int[,] dp = new int[n, 2];
        for (int i = 0; i < n; i++) {
            dp[i, 0] = -1;
            dp[i, 1] = -1;
        }
        return findProfit(0, 1, arr, dp);
    }


//Driver Code Starts
    public static void Main() {
        int[] arr = {0, 2, 1, 2, 3};

        Console.WriteLine(maxProfit(arr));
    }
}

//Driver Code Ends

JavaScript

// Recursive function with memoization to find profit
function findProfit(i, buy, arr, dp) {
    const n = arr.length;

    // Base case
    if (i >= n) return 0;

    // If already computed
    if (dp[i][buy] !== -1) return dp[i][buy];

    // If we can buy
    if (buy) {
        let take = -arr[i] + findProfit(i + 1, 0, arr, dp);
        let skip = findProfit(i + 1, 1, arr, dp);
        dp[i][buy] = Math.max(take, skip);
    }

    // If we can sell
    else {
        let sell = arr[i] + findProfit(i + 2, 1, arr, dp);
        let skip = findProfit(i + 1, 0, arr, dp);
        dp[i][buy] = Math.max(sell, skip);
    }

    return dp[i][buy];
}

// Function to find maximum profit
function maxProfit(arr) {
    const n = arr.length;
    const dp = Array.from({ length: n }, () => Array(2).fill(-1));
    return findProfit(0, 1, arr, dp);
}


// Driver Code
//Driver Code Starts
const arr = [0, 2, 1, 2, 3];
console.log(maxProfit(arr));

//Driver Code Ends

Output

[Better Approach 2] Using Bottom Up Dp (Tabulation) - O(n) Time and O(n) Space

The idea is to use tabulation (bottom-up DP) approach and build the solution iteratively.

We create a 2D DP table dp[i][buy] where:

dp[i][1] represents the maximum profit starting from day i when we can buy.
dp[i][0] represents the maximum profit starting from day i when we can sell.

We fill this table from the last day toward the first because each state depends on future days (i+1 or i+2).

At each step:

If we can buy, we choose between buying (-arr[i] + dp[i+1][0]) or skipping (dp[i+1][1]).
If we can sell, we choose between selling (arr[i] + dp[i+2][1]) or skipping (dp[i+1][0]).

The final answer will be stored in dp[0][1], which represents the maximum profit starting from the first day when buying is allowed.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//Driver Code Ends


int maxProfit(vector<int>& arr) {
    
    int n = arr.size();

    vector<vector<int>> dp(n + 2, vector<int>(2, 0));

    for (int i = n - 1; i >= 0; i--) {

        // When we can buy
        dp[i][1] = max(-arr[i] + dp[i + 1][0], dp[i + 1][1]);

        // When we can sell
        dp[i][0] = max(arr[i] + dp[i + 2][1], dp[i + 1][0]);
    }

    return dp[0][1];
}


//Driver Code Starts
int main() {
    vector<int> arr = {0, 2, 1, 2, 3};

    cout << maxProfit(arr);
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
class GFG {
//Driver Code Ends


    static int maxProfit(int[] arr) {

        int n =  arr.length;
        int[][] dp = new int[n + 2][2];

        for (int i = n - 1; i >= 0; i--) {

            // When we can buy
            dp[i][1] = Math.max(-arr[i] + dp[i + 1][0], dp[i + 1][1]);

            // When we can sell
            dp[i][0] = Math.max(arr[i] + dp[i + 2][1], dp[i + 1][0]);
        }

        return dp[0][1];
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {0, 2, 1, 2, 3};
        System.out.print(maxProfit(arr));
    }
}

//Driver Code Ends

Python

def maxProfit(arr):
    n = len(arr)

    dp = [[0 for _ in range(2)] for _ in range(n + 2)]

    for i in range(n - 1, -1, -1):

        # When we can buy
        dp[i][1] = max(-arr[i] + dp[i + 1][0], dp[i + 1][1])

        # When we can sell
        dp[i][0] = max(arr[i] + dp[i + 2][1], dp[i + 1][0])

    return dp[0][1]



#Driver Code Starts
if __name__ == "__main__":
    arr = [0, 2, 1, 2, 3]
    print(maxProfit(arr))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends

    
    static int maxProfit(int[] arr) {
        int n =  arr.Length;
        int[,] dp = new int[n + 2, 2];

        for (int i = n - 1; i >= 0; i--) {
            
            // When we can buy
            dp[i, 1] = Math.Max(-arr[i] + dp[i + 1, 0], dp[i + 1, 1]);

            // When we can sell
            dp[i, 0] = Math.Max(arr[i] + dp[i + 2, 1], dp[i + 1, 0]);
        }

        return dp[0, 1];
    }

//Driver Code Starts

    static void Main() {
        int[] arr = { 0, 2, 1, 2, 3 };
        Console.WriteLine(maxProfit(arr));
    }
}
//Driver Code Ends

JavaScript

function maxProfit(arr) {

    const n = arr.length;
    const dp = Array.from({ length: n + 2 }, () => [0, 0]);

    for (let i = n - 1; i >= 0; i--) {

        // When we can buy
        dp[i][1] = Math.max(-arr[i] + dp[i + 1][0], dp[i + 1][1]);

        // When we can sell
        dp[i][0] = Math.max(arr[i] + dp[i + 2][1], dp[i + 1][0]);
    }

    return dp[0][1];
}


//Driver Code Starts
// Driver Code
const arr = [0, 2, 1, 2, 3];
console.log(maxProfit(arr));

//Driver Code Ends

Output

[Expected Approach] Using Space Optimization - O(n) Time and O(1) Space

In the tabulation (bottom-up) approach, we used a 2D dp array of size (n + 2) × 2 — where each cell dp[i][buy] stored the maximum profit from day i onward.

But if you observe carefully, to compute dp[i][buy], we only need the values from dp[i + 1] and dp[i + 2].

So, instead of storing the entire table, we can just keep track of:
ahead1 → the results of the next day (dp[i + 1])
ahead2 → the results of the day after next (dp[i + 2])
curr → the current day results (dp[i])

This way, we iteratively calculate results from the end (last day) toward the beginning while reusing only these three arrays.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//Driver Code Ends


int maxProfit(vector<int>& arr) {
    int n = arr.size();
    
    vector<int> ahead1(2, 0), ahead2(2, 0), curr(2, 0);

    for (int i = n - 1; i >= 0; i--) {

        // When we can buy
        curr[1] = max(-arr[i] + ahead1[0], ahead1[1]);

        // When we can sell
        curr[0] = max(arr[i] + ahead2[1], ahead1[0]);

        ahead2 = ahead1;
        ahead1 = curr;
    }

    return ahead1[1];
}

//Driver Code Starts

int main() {
    vector<int> arr = {0, 2, 1, 2, 3};

    cout << maxProfit(arr);
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.Arrays;

class GFG {
//Driver Code Ends


    static int maxProfit(int[] arr) {
        int n = arr.length;
        int[] ahead1 = new int[2];
        int[] ahead2 = new int[2];
        int[] curr = new int[2];

        for (int i = n - 1; i >= 0; i--) {

            // When we can buy
            curr[1] = Math.max(-arr[i] + ahead1[0], ahead1[1]);

            // When we can sell
            curr[0] = Math.max(arr[i] + ahead2[1], ahead1[0]);

            ahead2 = ahead1.clone();
            ahead1 = curr.clone();
        }

        return ahead1[1];
    }


//Driver Code Starts
    public static void main(String[] args) {
        int[] arr = {0, 2, 1, 2, 3};

        System.out.println(maxProfit(arr));
    }
}

//Driver Code Ends

Python

def maxProfit(arr):
    n = len(arr)
    ahead1 = [0, 0]
    ahead2 = [0, 0]
    curr = [0, 0]

    for i in range(n - 1, -1, -1):

        # When we can buy
        curr[1] = max(-arr[i] + ahead1[0], ahead1[1])

        # When we can sell
        curr[0] = max(arr[i] + ahead2[1], ahead1[0])

        ahead2 = ahead1[:]
        ahead1 = curr[:]

    return ahead1[1]


#Driver Code Starts
if __name__ == "__main__":
    arr = [0, 2, 1, 2, 3]
    print(maxProfit(arr))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int maxProfit(int[] arr) {
        int n = arr.Length;
        int[] ahead1 = new int[2];
        int[] ahead2 = new int[2];
        int[] curr = new int[2];

        for (int i = n - 1; i >= 0; i--) {

            // When we can buy
            curr[1] = Math.Max(-arr[i] + ahead1[0], ahead1[1]);

            // When we can sell
            curr[0] = Math.Max(arr[i] + ahead2[1], ahead1[0]);

            ahead2 = (int[])ahead1.Clone();
            ahead1 = (int[])curr.Clone();
        }

        return ahead1[1];
    }


//Driver Code Starts
    public static void Main() {
        int[] arr = {0, 2, 1, 2, 3};

        Console.WriteLine(maxProfit(arr));
    }
}

//Driver Code Ends

JavaScript

function maxProfit(arr) {
    let n = arr.length;
    let ahead1 = [0, 0];
    let ahead2 = [0, 0];
    let curr = [0, 0];

    for (let i = n - 1; i >= 0; i--) {

        // When we can buy
        curr[1] = Math.max(-arr[i] + ahead1[0], ahead1[1]);

        // When we can sell
        curr[0] = Math.max(arr[i] + ahead2[1], ahead1[0]);

        ahead2 = [...ahead1];
        ahead1 = [...curr];
    }

    return ahead1[1];
}


//Driver Code Starts
// Driver Code
const arr = [0, 2, 1, 2, 3];
console.log(maxProfit(arr));

//Driver Code Ends

Output

Stock Buy and Sell with Cooldown

[Naive Approach] Using Recursion - O(2n) Time and O(n) Space

[Better Approach 1] Using Top Down Dp (Memorization) - O(n) Time and O(n) Space

[Better Approach 2] Using Bottom Up Dp (Tabulation) - O(n) Time and O(n) Space

[Expected Approach] Using Space Optimization - O(n) Time and O(1) Space

Explore

[Naive Approach] Using Recursion - O(2ⁿ) Time and O(n) Space