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 = 87Input: prices[] = [90, 80, 70, 60, 50], k = 1
Output: 0
Explanation: Not possible to earn.
Table of Content
[Naive Approach] Using Recursion - O(2n) time and O(n) space
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.
//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
//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
# 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
//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
// 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])
//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
//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
# 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
//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
// 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.
//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
//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
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
//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
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.
//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
//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
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
//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
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