Stock Buy and Sell - At most k Transactions Allowed

Last Updated : 4 Nov, 2025

Given an array prices[], where prices[i] represents the price of a stock on the i-th day, and an integer k representing the maximum number of transactions allowed, find the maximum profit that can be earned by performing at most k transactions.

Each transaction consists of one buy and one sell operation, and a new transaction can begin only after the previous one is completed.

Examples:

Input: prices[] = [10, 22, 5, 80], k = 2
Output: 87
Explanation: Buy on 1st day at 10 and sell on 2nd day at 22. Then, again buy on 3rd day at 5 and sell on 4th day at 80. Total profit = 12 + 75 = 87

Input: prices[] = [90, 80, 70, 60, 50], k = 1
Output: 0
Explanation: Not possible to earn.

Try it on GfG Practice
redirect icon

The idea is to recursively explore all possible buy and sell decisions to find the maximum profit. To do this, we use a variable buy, which is set to 1 if we can buy a stock and 0 if we must sell the currently held one.

We start from the 0th index, and for each day i, there are two choices depending on the current state:

  • If we can buy (buy == 1): We can either buy the stock today or skip the day.
    profit(i, k, 1) = max(-prices[i] + profit(i + 1, k, 0), profit(i + 1, k, 1))
  • If we can sell (buy == 0): We can either sell the stock today or skip the day.
    profit(i, k, 0) = max(prices[i] + profit(i + 1, k - 1, 1), profit(i + 1, k, 0))

The recursion terminates when all days are processed (i >= n) or no transactions remain (k <= 0), returning 0 in such cases.

C++
//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Driver Code Ends


// Utility function for recursive profit calculation
int maxProfitUtil(int i, int k, int buy, vector<int> &prices) {

    // Base case
    if (k <= 0 || i >= prices.size()) return 0;

    int res = 0;

    // If we can buy, choose to buy or skip
    if (buy)
        res = max(maxProfitUtil(i + 1, k, 0, prices) - prices[i],
                  maxProfitUtil(i + 1, k, 1, prices));

    // If we can sell, choose to sell or skip
    else
        res = max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices),
                  maxProfitUtil(i + 1, k, 0, prices));

    return res;
}

// Function to return maximum profit with k transactions
int maxProfit(vector<int> &prices, int k) {
    return maxProfitUtil(0, k, 1, prices);
}


//Driver Code Starts
int main() {
    int k = 2;
    vector<int> prices = {10, 22, 5, 80};

    cout << maxProfit(prices, k);
    return 0;
}

//Driver Code Ends
Java
//Driver Code Starts
import java.util.ArrayList;

class GFG {
//Driver Code Ends

    
    // Utility function for recursive profit calculation
    static int maxProfitUtil(int i, int k, int buy, int[] prices) {

        // Base case
        if (k <= 0 || i >= prices.length) return 0;

        int res = 0;

        // If we can buy, choose to buy or skip
        if (buy == 1)
            res = Math.max(maxProfitUtil(i + 1, k, 0, prices) - prices[i],
                           maxProfitUtil(i + 1, k, 1, prices));

        // If we can sell, choose to sell or skip
        else
            res = Math.max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices),
                           maxProfitUtil(i + 1, k, 0, prices));

        return res;
    }
    
    // Function to return maximum profit with k transactions
    static int maxProfit(int[] prices, int k) {
        return maxProfitUtil(0, k, 1, prices);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int k = 2;
        int[] prices = {10, 22, 5, 80};

        System.out.println(maxProfit(prices, k));
    }
}

//Driver Code Ends
Python
# Utility function for recursive profit calculation
def maxProfitUtil(i, k, buy, prices):

    # Base case
    if k <= 0 or i >= len(prices):
        return 0

    # If we can buy, choose to buy or skip
    if buy:
        res = max(maxProfitUtil(i + 1, k, 0, prices) - prices[i],
                  maxProfitUtil(i + 1, k, 1, prices))
    # If we can sell, choose to sell or skip
    else:
        res = max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices),
                  maxProfitUtil(i + 1, k, 0, prices))

    return res

# Function to return maximum profit with k transactions
def maxProfit(prices, k):
    return maxProfitUtil(0, k, 1, prices)



#Driver Code Starts
if __name__ == "__main__":
    k = 2
    prices = [10, 22, 5, 80]
    print(maxProfit(prices, k))

#Driver Code Ends
C#
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends


    // Utility function to calculate maximum profit recursively
    static int maxProfitUtil(int i, int k, int buy, int[] prices) {

        // Base case
        if (k <= 0 || i >= prices.Length)
            return 0;

        int res;

        // If we can buy, choose to buy or skip
        if (buy == 1)
            res = Math.Max(maxProfitUtil(i + 1, k, 0, prices) - prices[i],
                           maxProfitUtil(i + 1, k, 1, prices));
        // If we can sell, choose to sell or skip
        else
            res = Math.Max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices),
                           maxProfitUtil(i + 1, k, 0, prices));

        return res;
    }

    // Function to return maximum profit with k transactions
    static int maxProfit(int[] prices, int k) {
        return maxProfitUtil(0, k, 1, prices);
    }


//Driver Code Starts
    static void Main() {
        int k = 2;
        int[] prices = {10, 22, 5, 80};
        Console.WriteLine(maxProfit(prices, k));
    }
}

//Driver Code Ends
JavaScript
// Utility function to calculate maximum profit recursively
function maxProfitUtil(i, k, buy, prices) {

    // Base case
    if (k <= 0 || i >= prices.length)
        return 0;

    let res;

    // If we can buy, choose to buy or skip
    if (buy)
        res = Math.max(maxProfitUtil(i + 1, k, 0, prices) - prices[i],
                       maxProfitUtil(i + 1, k, 1, prices));

    // If we can sell, choose to sell or skip
    else
        res = Math.max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices),
                       maxProfitUtil(i + 1, k, 0, prices));

    return res;
}

// Function to return maximum profit with k transactions
function maxProfit(prices, k) {
    return maxProfitUtil(0, k, 1, prices);
}


// Driver Code
//Driver Code Starts
const k = 2;
const prices = [10, 22, 5, 80];
console.log(maxProfit(prices, k));

//Driver Code Ends

Output
87

[Better Approach-1] Using Memoization - O(n*k) time and O(n*k) space

We optimize the recursive solution by storing results of overlapping subproblems in a 3D array dp[i][k][buy], where:

  • i → current day
  • k → remaining transactions
  • buy → 1 if we can buy, else 0

Before computing a state, we check if it’s already solved to avoid recomputation.

Recurrence:

If buy == 1:

    dp[i][k][1] = max(-prices[i] + dp[i + 1][k][0], dp[i + 1][k][1])

Else:

    dp[i][k][0] = max(prices[i] + dp[i + 1][k - 1][1], dp[i + 1][k][0])

C++
//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Driver Code Ends


// Recursive function with memoization
int maxProfitUtil(int i, int k, int buy, vector<int> &prices, 
                                vector<vector<vector<int>>> &dp) {

    // Base case
    if (k <= 0 || i >= prices.size()) return 0;

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

    int res = 0;

    // If we can buy
    if (buy)
        res = max(-prices[i] + maxProfitUtil(i + 1, k, 0, prices, dp),
                  maxProfitUtil(i + 1, k, 1, prices, dp));

    // If we can sell
    else
        res = max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices, dp),
                  maxProfitUtil(i + 1, k, 0, prices, dp));

    return dp[i][k][buy] = res;
}

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


//Driver Code Starts
int main() {
    int k = 2;
    vector<int> prices = {10, 22, 5, 80};

    cout << maxProfit(prices, k);
    return 0;
}
//Driver Code Ends
Java
//Driver Code Starts
import java.util.Arrays;

class GFG {
//Driver Code Ends


    // Recursive function with memoization
    static int maxProfitUtil(int i, int k, int buy, int[] prices, int[][][] dp) {

        // Base case
        if (k <= 0 || i >= prices.length) return 0;

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

        int res = 0;

        // If we can buy
        if (buy == 1)
            res = Math.max(-prices[i] + maxProfitUtil(i + 1, k, 0, prices, dp),
                           maxProfitUtil(i + 1, k, 1, prices, dp));

        // If we can sell
        else
            res = Math.max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices, dp),
                           maxProfitUtil(i + 1, k, 0, prices, dp));

        return dp[i][k][buy] = res;
    }

    // Function to find maximum profit
    static int maxProfit(int[] prices, int k) {
        int n = prices.length;
        int[][][] dp = new int[n][k + 1][2];
        for (int[][] arr : dp)
            for (int[] row : arr)
                Arrays.fill(row, -1);
        return maxProfitUtil(0, k, 1, prices, dp);
    }


//Driver Code Starts
    public static void main(String[] args) {
        int k = 2;
        int[] prices = {10, 22, 5, 80};

        System.out.println(maxProfit(prices, k));
    }
}

//Driver Code Ends
Python
# Recursive function with memoization
def maxProfitUtil(i, k, buy, prices, dp):

    # Base case
    if k <= 0 or i >= len(prices):
        return 0

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

    res = 0

    # If we can buy
    if buy:
        res = max(-prices[i] + maxProfitUtil(i + 1, k, 0, prices, dp),
                  maxProfitUtil(i + 1, k, 1, prices, dp))

    # If we can sell
    else:
        res = max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices, dp),
                  maxProfitUtil(i + 1, k, 0, prices, dp))

    dp[i][k][buy] = res
    return res


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



#Driver Code Starts
if __name__ == "__main__":
    k = 2
    prices = [10, 22, 5, 80]
    print(maxProfit(prices, k))

#Driver Code Ends
C#
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends

    
    // Recursive function with memoization
    static int maxProfitUtil(int i, int k, int buy, int[] prices, int[,,] dp) {
        
        // Base case
        if (k <= 0 || i >= prices.Length) return 0;

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

        int res = 0;

        // If we can buy
        if (buy == 1)
            res = Math.Max(-prices[i] + maxProfitUtil(i + 1, k, 0, prices, dp),
                           maxProfitUtil(i + 1, k, 1, prices, dp));

        // If we can sell
        else
            res = Math.Max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices, dp),
                           maxProfitUtil(i + 1, k, 0, prices, dp));

        dp[i, k, buy] = res;
        return res;
    }

    // Function to find maximum profit
    static int maxProfit(int[] prices, int k) {
        int n = prices.Length;
        int[,,] dp = new int[n, k + 1, 2];

        for (int i = 0; i < n; i++)
            for (int j = 0; j <= k; j++)
                for (int b = 0; b < 2; b++)
                    dp[i, j, b] = -1;

        return maxProfitUtil(0, k, 1, prices, dp);
    }


//Driver Code Starts
    static void Main() {
        int k = 2;
        int[] prices = { 10, 22, 5, 80 };
        Console.WriteLine(maxProfit(prices, k));
    }
}
//Driver Code Ends
JavaScript
// Recursive function with memoization
function maxProfitUtil(i, k, buy, prices, dp) {

    // Base case
    if (k <= 0 || i >= prices.length) return 0;

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

    let res = 0;

    // If we can buy
    if (buy)
        res = Math.max(-prices[i] + maxProfitUtil(i + 1, k, 0, prices, dp),
                       maxProfitUtil(i + 1, k, 1, prices, dp));
    else
        res = Math.max(prices[i] + maxProfitUtil(i + 1, k - 1, 1, prices, dp),
                       maxProfitUtil(i + 1, k, 0, prices, dp));

    dp[i][k][buy] = res;
    return res;
}

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


// Driver Code
//Driver Code Starts
const k = 2;
const prices = [10, 22, 5, 80];
console.log(maxProfit(prices, k));

//Driver Code Ends

Output
87

[Better Approach-2] Using Bottom Up DP - O(n*k) time and O(n*k) space

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

We create a 3D array dp[n+1][k+1][2], where each state represents:

  • i → current day (0 to n-1)
  • k → number of transactions remaining
  • buy → whether we can buy (1) or sell (0)

We fill the table starting from the last day towards the first, since the profit of the current day depends on future states.
For each state, we compute:

  • If we can buy → dp[i][k][1] = max(-prices[i] + dp[i+1][k][0], dp[i+1][k][1])
  • If we can sell → dp[i][k][0] = max(prices[i] + dp[i+1][k-1][1], dp[i+1][k][0])

Finally, dp[0][K][1] gives the maximum profit starting from day 0 with the option to buy.


C++
//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Driver Code Ends


int maxProfit(vector<int> &prices, int k) {

    int n = prices.size();

    // Create dp table
    vector<vector<vector<int>>> dp(n + 1, 
            vector<vector<int>>(k + 1, vector<int>(2, 0)));

    // Traverse from last day to first
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 1; j <= k; j++) {

            // If we can buy
            dp[i][j][1] = max(-prices[i] + dp[i + 1][j][0],
                               dp[i + 1][j][1]);

            // If we can sell
            dp[i][j][0] = max(prices[i] + dp[i + 1][j - 1][1],
                               dp[i + 1][j][0]);
        }
    }

    // Return answer for day 0 with full transactions and buy allowed
    return dp[0][k][1];
}


//Driver Code Starts
int main() {
    int k = 2;
    vector<int> prices = {10, 22, 5, 80};

    cout << maxProfit(prices, k);
    return 0;
}

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


    static int maxProfit(int[] prices, int k) {

        int n = prices.length;

        // Create dp table
        int[][][] dp = new int[n + 1][k + 1][2];

        // Traverse from last day to first
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= k; j++) {

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

                // If we can sell
                dp[i][j][0] = Math.max(prices[i] + dp[i + 1][j - 1][1],
                                         dp[i + 1][j][0]);
            }
        }

        // Return answer for day 0 with full transactions and buy allowed
        return dp[0][k][1];
    }


//Driver Code Starts
    public static void main(String[] args) {
        int k = 2;
        int[] prices = {10, 22, 5, 80};

        System.out.println(maxProfit(prices, k));
    }
}
//Driver Code Ends
Python
def maxProfit(prices, k):

    n = len(prices)

    # Create dp table
    dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]

    # Traverse from last day to first
    for i in range(n - 1, -1, -1):
        for j in range(1, k + 1):

            # If we can buy
            dp[i][j][1] = max(-prices[i] + dp[i + 1][j][0],
                               dp[i + 1][j][1])

            # If we can sell
            dp[i][j][0] = max(prices[i] + dp[i + 1][j - 1][1],
                               dp[i + 1][j][0])

    # Return answer for day 0 with full transactions and buy allowed
    return dp[0][k][1]


if __name__ == '__main__':
#Driver Code Starts
    k = 2
    prices = [10, 22, 5, 80]
    print(maxProfit(prices, k))

#Driver Code Ends
C#
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends


    static int maxProfit(int[] prices, int k) {

        int n = prices.Length;

        // Create dp table
        int[,,] dp = new int[n + 1, k + 1, 2];

        // Traverse from last day to first
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= k; j++) {

                // If we can buy
                dp[i, j, 1] = Math.Max(-prices[i] + dp[i + 1, j, 0],
                                        dp[i + 1, j, 1]);

                // If we can sell
                dp[i, j, 0] = Math.Max(prices[i] + dp[i + 1, j - 1, 1],
                                        dp[i + 1, j, 0]);
            }
        }

        // Return answer for day 0 with full transactions and buy allowed
        return dp[0, k, 1];
    }


//Driver Code Starts
    static void Main() {
        int k = 2;
        int[] prices = {10, 22, 5, 80};

        Console.WriteLine(maxProfit(prices, k));
    }
}

//Driver Code Ends
JavaScript
function maxProfit(prices, k) {

    const n = prices.length;

    // Create dp table
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: k + 1 }, () => [0, 0])
    );

    // Traverse from last day to first
    for (let i = n - 1; i >= 0; i--) {
        for (let j = 1; j <= k; j++) {

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

            // If we can sell
            dp[i][j][0] = Math.max(prices[i] + dp[i + 1][j - 1][1],
                                    dp[i + 1][j][0]);
        }
    }

    // Return answer for day 0 with full transactions and buy allowed
    return dp[0][k][1];
}


// Driver code
//Driver Code Starts
let k = 2;
let prices = [10, 22, 5, 80];
console.log(maxProfit(prices, k));

//Driver Code Ends

Output
87

[Expected Approach] Space Optimized - O(n*k) time and O(k) space

Since on any day we only depend on the results of the next day, we can reduce the 3D DP table to two 2D arrays — ahead (for day i+1) and curr (for day i).

Each has dimensions [k+1][2], representing remaining transactions and buy/sell state.

For each day (from last to first):

  • If we can buy, we take the maximum of:
    Buying the stock now → -prices[i] + ahead[k][0]
    Skipping → ahead[k][1]
  • If we can sell, we take the maximum of:
    Selling the stock now → prices[i] + ahead[k - 1][1]
    Skipping → ahead[k][0]

After processing each day, curr becomes the new ahead. Finally, ahead[k][1] gives the maximum profit possible.

C++
//Driver Code Starts
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Driver Code Ends


int maxProfit(vector<int> &prices, int k) {
    int n = prices.size();

    vector<vector<int>> ahead(k + 1, vector<int>(2, 0)),
                                curr(k + 1, vector<int>(2, 0));

    for (int i = n - 1; i >= 0; i--) {
        for (int t = 1; t <= k; t++) {

            // If we can buy
            curr[t][1] = max(-prices[i] + ahead[t][0], ahead[t][1]);

            // If we can sell
            curr[t][0] = max(prices[i] + ahead[t - 1][1], ahead[t][0]);
        }
        ahead = curr;
    }

    return ahead[k][1];
}

int main() {
    int k = 2;
    vector<int> prices = {10, 22, 5, 80};

//Driver Code Starts

    cout << maxProfit(prices, k);
    return 0;
}

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


    static int maxProfit(int[] prices, int k) {
        int n = prices.length;

        int[][] ahead = new int[k + 1][2];
        int[][] curr = new int[k + 1][2];

        // Traverse days from end to start
        for (int i = n - 1; i >= 0; i--) {

            // Traverse all transactions
            for (int t = 1; t <= k; t++) {

                // If we can buy
                curr[t][1] = Math.max(-prices[i] + ahead[t][0], ahead[t][1]);

                // If we can sell
                curr[t][0] = Math.max(prices[i] + ahead[t - 1][1], ahead[t][0]);
            }

            ahead = curr.clone();
        }

        return ahead[k][1];
    }


//Driver Code Starts
    public static void main(String[] args) {
        int k = 2;
        int[] prices = {10, 22, 5, 80};
        System.out.println(maxProfit(prices, k));
    }
}

//Driver Code Ends
Python
def maxProfit(prices, k):

    n = len(prices)
    ahead = [[0 for _ in range(2)] for _ in range(k + 1)]
    curr = [[0 for _ in range(2)] for _ in range(k + 1)]

    # Traverse days in reverse order
    for i in range(n - 1, -1, -1):

        for j in range(1, k + 1):

            # If we can buy
            buy = max(-prices[i] + ahead[j][0],
                      ahead[j][1])

            # If we can sell
            sell = max(prices[i] + ahead[j - 1][1],
                       ahead[j][0])

            curr[j][1] = buy
            curr[j][0] = sell

        ahead = [row[:] for row in curr]

    return ahead[k][1]



if __name__ == '__main__':
#Driver Code Starts
    k = 2
    prices = [10, 22, 5, 80]
    print(maxProfit(prices, k))

#Driver Code Ends
C#
//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int maxProfit(int[] prices, int k) {
        int n = prices.Length;

        int[,] ahead = new int[k + 1, 2];
        int[,] curr = new int[k + 1, 2];

        // Traverse days from end to start
        for (int i = n - 1; i >= 0; i--) {

            // Traverse all transactions
            for (int t = 1; t <= k; t++) {

                // If we can buy
                curr[t, 1] = Math.Max(-prices[i] + ahead[t, 0], ahead[t, 1]);

                // If we can sell
                curr[t, 0] = Math.Max(prices[i] + ahead[t - 1, 1], ahead[t, 0]);
            }

            for (int t = 0; t <= k; t++) {
                ahead[t, 0] = curr[t, 0];
                ahead[t, 1] = curr[t, 1];
            }
        }

        return ahead[k, 1];
    }


//Driver Code Starts
    public static void Main() {
        int k = 2;
        int[] prices = {10, 22, 5, 80};
        Console.WriteLine(maxProfit(prices, k));
    }
}

//Driver Code Ends
JavaScript
function maxProfit(prices, k) {

    const n = prices.length;
    let ahead = Array.from({ length: k + 1 }, () => [0, 0]);
    let curr = Array.from({ length: k + 1 }, () => [0, 0]);

    // Traverse days in reverse order
    for (let i = n - 1; i >= 0; i--) {

        for (let j = 1; j <= k; j++) {

            // If we can buy
            let buy = Math.max(-prices[i] + ahead[j][0],
                               ahead[j][1]);

            // If we can sell
            let sell = Math.max(prices[i] + ahead[j - 1][1],
                                ahead[j][0]);

            curr[j][1] = buy;
            curr[j][0] = sell;
        }

        ahead = curr.map(row => [...row]);
    }

    return ahead[k][1];
}


// Driver code
//Driver Code Starts
const k = 2;
const prices = [10, 22, 5, 80];
console.log(maxProfit(prices, k));

//Driver Code Ends

Output
87

Releated Problems
Stock Buy and Sell – Max 2 Transactions Allowed
Stock Buy and Sell - Multiple Transactions Allowed

Comment