×

Search anything:

# Maximum Profit by Buying and Selling a Share at Most k Times

#### Algorithms Dynamic Programming (DP) backtracking

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article at OpenGenus, we will solve the problem of getting maximum profit by buying and selling a share at most k times. The article will guide you through the intuition of how to solve the problem using the concept of backtracking and dynamic programming which is frequently asked in coding interviews of various tech companies.

1. Problem Statement
2. Intuition behind using Backtracking
3. Why need Dynamic Programming ?
4. Implementing the Solution
5. Time and Space Complexity

# 1. Problem Statement

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day, and an integer `k`.

Find the maximum profit you can achieve. You may complete at most `k` transactions: i.e. you may buy at most `k` times and sell at most `k` times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Let's understand the problem with an example :

Suppose we are given the `k` = 2, `prices` = [3 ,2 ,6 ,5 ,0 ,3 ] , which means we can make at most 2 transactions and we have to generate the maximum profit in at most 2 transactions not more than that, which implies that we can buy and sell at most 2 times.So for instance I can buy on day 1 and sell on day 4 which completes one transaction and for second transaction we can buy on day 5 and sell on day 7. Also there is a condition that we have to sell the stock first and then buy again which means if I buy on day 1 then I can not buy again until I sell it. So for the above problem we have following cases :

1. `Buy on Day 1` :

Buy on Day 1 with a price of 3 and now we want to sell the stock for some profit. Therefore as we can see the `prices` list one of the choice to sell the Day 3 or Day 4 with some profit or make zero profit on Day 6. Let's explore the choices one by one :

1.1. `Sell on Day 3` : Sell on day 3 make `profit` of 6-3 = 3.

• 1.1.1. Now choose next day to buy as we can make 1 more transaction as value of k was 2. The k is now 1. So we can either make profit of 3 and stop here or continue to make one more transaction.
• 1.1.2. Let's see the choice of next Buy day which are : day 4 , day 5 , day 6. So if we buy on day 4 , at price 5 then we can't sell it profitably on day 5 and day 6. So, let's explore the next choice of buying at day 5 at price 0 and sell on day 6, therefore profit is 3 - 0 = 3. Therefore `profit` = 3 + 3 = 6 total.

1.2. `Sell on Day 4` : Sell on day 4 with `profit` of 5-3 = 2.

• 1.2.1 Now choose next day to buy as we can make 1 more transaction as value of k was 3. The k is now 1. So we can either make profit of 2 and stop here or continue to make one more transaction.
• 1.2.2. Let's see the choice of next Buy day which are : day 5 , day 6. So if we buy on day 5 , at price 0 and sell on day 6, therefore profit is 3 - 0 = 3. Therefore `profit` = 2 + 3 = 5 total.

1.3. `Sell on Day 6` : We make a profit 0, and we stop here as there no more days left.

2. `Buy on Day 2` : The above same process goes and we keep track of maximum profit.
.
.
.
.

3. `Buy on Day 6` : The above same process goes and we keep track of maximum profit.

# 2. Intuition behind using Backtracking

Suppose we are given the `k` = 2, `prices` = [3 ,2 ,6 ,5 ,0 ,3 ] ,
which means that we are given the prices of the share at different point of times and we can buy and sell only 2 times.

One of the possible solution for the above example is :

1. We can buy the buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
2. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Here we are making choices where we choose to buy on `ith` day and sell on `jth` day with a profit `p` and we can do this process at most `'k'` times. This will lead us to a dependency tree of choices. We may need to backtrack both buy and sell choices. The figure below shows the tree if we choose the day 1 as buy choice.

The green edge is the maximum profit edge. We backtrack the first two edges which are highlighted in red and take the maximum out of the three edges. Therefore the maximum profit if we buy on day 1 at price 3 and sell on day 2 with price 2 we get a profit of 4. Similar tree will grow for the sell at day 3 and so. But note that the tree will only grow upto 2 levels only as k = 2.The code using backtracking is as follows :

``````class Solution {
public:

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

// passing index , k , prices
return solve(0, k, prices);
}

int solve(int index, int k, vector<int>& prices) {

// if we have k transactions we can stop
if (k == 0) {
return 0;
}
// if we have seen all the days we can stop
if (index >= prices.size()) {
return 0;
}

// We need to find the maximum profit by either skipping the current day
// (i.e., not making any transaction on this day) or making a transaction
// on this day and then finding the maximum profit for the remaining days.

// skipping the current day and keeping the k same as no transaction is made
int maxProfitWithoutTransaction = solve(index + 1, k, prices);

// if we make the transaction on the index day what will be the maximum profit
int maxProfitWithTransaction = 0;

// if index is the day of buying we are finding the ith day on which we can sell and calucate profit for next k-1 transactions starting from i+1
for (int i = index + 1; i < prices.size(); i++) {

int profit = prices[i] - prices[index];
if (profit >= 0) {
int nextProfit = solve(i + 1, k - 1, prices);
maxProfitWithTransaction = max(maxProfitWithTransaction, profit + nextProfit);

}
}

return max(maxProfitWithoutTransaction, maxProfitWithTransaction);
}
};
``````

The given code is a C++ implementation of a solution to find the maximum profit that can be obtained from at most `k` transactions in a stock market. The stock prices are given as an array `prices`, where `prices[i]` represents the price of the stock on the ith day.

The solution uses a recursive approach to explore all possible transactions and find the maximum profit. The `maxProfit` function serves as a driver function, and it initializes the recursive process by calling the `solve` function with initial parameters.

The `solve` function takes three parameters:

1. `index`: The current index or day in the `prices` array.
2. `k`: The remaining number of transactions allowed.
3. `prices`: The array of stock prices.

The base cases are checked first:

• If `k` becomes 0 (no more transactions allowed), the function returns 0.
• If the `index` goes beyond the size of the `prices` array, meaning all days have been considered, the function returns 0.

The main logic involves finding the maximum profit by either skipping the current day (no transaction) or making a transaction on the current day and finding the maximum profit for the remaining days. The maximum profit without the current transaction is calculated by recursively calling the function with the next index and the same `k`. The maximum profit with the current transaction involves iterating over the remaining days, calculating the profit if a transaction is made on the current day, and recursively finding the maximum profit for the remaining transactions.

The line `maxProfitWithTransaction = max(maxProfitWithTransaction, profit + nextProfit);` updates the maximum profit with the current transaction if the calculated profit on the current day is greater than the current maximum.

The function returns the maximum profit among the two cases: with and without the current transaction.

## Complexity Analysis :

The time and space complexity as follows :

1.Time Complexity: The time complexity of the code is exponential, specifically O(2^n), where 'n' is the number of days (size of the input vector prices). This is because the code explores all possible combinations of making transactions or not making transactions on each day, and the recursive calls lead to an exponential number of function calls.

1. Size Complexity : The space complexity is determined by the depth of the recursion, which is influenced by the number of transactions 'k'. In the worst case, the recursion depth can be 'k', as the algorithm explores k transactions.

It's worth noting that this solution has exponential time complexity, as it explores all possible combinations of transactions. For large inputs, it may be inefficient, and dynamic programming techniques like memoization or tabulation could be applied to optimize the solution.

# 3. Why need Dynamic Programming ?

Since the tree may grow too much with different branches and branches may get reused. So we need the dynamic programming to cache the results from different branches. We will need a two dimensional grid to do so. As the one dimension will be used to keep track of each day and the second dimension will be used to keep track of the `k` which means that how many choices more we can make at the current day.

Therefore the code in backtracking optimized with the dynamic programming is as follows :

``````class Solution {
public:

// 2D Dynamic Programming dp[index][k]
vector<vector<int>> dp;

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

int n = prices.size();
dp.resize(n, vector<int>(k+1 , -1));
// passing index , k , prices
return solve(0, k, prices);
}

int solve(int index, int k, vector<int>& prices) {

// if we have k transactions we can stop
if (k == 0) {
return 0;
}
// if we have seen all the days we can stop
if (index >= prices.size()) {
return 0;
}
// if we have cached result means we have seen the branch we reuse it
if (dp[index][k] != -1) {
return dp[index][k];
}

// We need to find the maximum profit by either skipping the current day
// (i.e., not making any transaction on this day) or making a transaction
// on this day and then finding the maximum profit for the remaining days.

// skipping the current day and keeping the k same as no transaction is made
int maxProfitWithoutTransaction = solve(index + 1, k, prices);

// if we make the transaction on the index day what will be the maximum profit
int maxProfitWithTransaction = 0;

// if index is the day of buying we are finding the ith day on which we can sell and calucate profit for next k-1 transactions starting from i+1
for (int i = index + 1; i < prices.size(); i++) {

int profit = prices[i] - prices[index];
if (profit >= 0) {
int nextProfit = solve(i + 1, k - 1, prices);
maxProfitWithTransaction = max(maxProfitWithTransaction, profit + nextProfit);

}
}

// caching the results into the dp
dp[index][k] = max(maxProfitWithoutTransaction, maxProfitWithTransaction);
return dp[index][k];
}
};
``````

This solution is a dynamic programming (DP) approach to solving the problem of finding the maximum profit that can be obtained from at most k transactions in a stock market, where stock prices are given as an array prices. The DP approach uses memoization to store the results of subproblems in a 2D array dp to avoid redundant calculations and improve efficiency.

# 4. Implementing the Solution

Therefore the complete implementation of the solution can be seen below where the Solution class is same as the dynamic programming and the added main function. The main function includes the call to `maxProfit` function.

``````#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// 2D Dynamic Programming dp[index][k]
vector<vector<int>> dp;

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

// Initialize the memoization table with -1 (unvisited) values
dp.resize(n, vector<int>(k + 1, -1));

// Call the recursive solve function to find the maximum profit
return solve(0, k, prices);
}

int solve(int index, int k, vector<int>& prices) {
// Base case: if no more transactions are allowed or all days are considered
if (k == 0 || index >= prices.size()) {
return 0;
}

// If the result for this subproblem is already calculated, return it
if (dp[index][k] != -1) {
return dp[index][k];
}

// We need to find the maximum profit by either skipping the current day
// (i.e., not making any transaction on this day) or making a transaction
// on this day and then finding the maximum profit for the remaining days.

// Calculate the maximum profit without making a transaction on the current day
int maxProfitWithoutTransaction = solve(index + 1, k, prices);

// Calculate the maximum profit with making a transaction on the current day
int maxProfitWithTransaction = 0;

// If index is the day of buying, find the day on which we can sell
for (int i = index + 1; i < prices.size(); i++) {
int profit = prices[i] - prices[index];

// Ensure a valid profit before considering it
if (profit >= 0) {
// Calculate the profit for the remaining transactions starting from i+1
int nextProfit = solve(i + 1, k - 1, prices);
// Update the maximum profit with the current transaction
maxProfitWithTransaction = max(maxProfitWithTransaction, profit + nextProfit);
}
}

// Cache the results into the dp table
dp[index][k] = max(maxProfitWithoutTransaction, maxProfitWithTransaction);

// Return the maximum profit for the current state
return dp[index][k];
}
};

int main() {
Solution solution;

// Example usage:
vector<int> prices = {3, 2, 6, 5, 0, 3};
int k = 2;

// Call the maxProfit method and print the result
int maxProfit = solution.maxProfit(k, prices);

cout << "Maximum Profit: " << maxProfit << endl;

return 0;
}

``````

Output :

``````Maximum Profit: 7
``````

# 5. Time and Space Complexity

Let's analyze the time and space complexity of the provided solution:

1. Time Complexity:

The time complexity of the solution is determined by the number of unique subproblems that need to be solved. Since the solution uses memoization to avoid redundant calculations, the time complexity is greatly reduced.

The time complexity is O(n * k), where:

• `n` is the number of days (length of the `prices` array).
• `k` is the maximum number of transactions allowed.

This is because, for each combination of `index` and `k`, the solution explores the possibilities of making or not making a transaction on a particular day. There are at most `n * k` unique subproblems, and each subproblem takes constant time to solve once it's memoized.

2. Space Complexity:

The space complexity is influenced by the memoization table (`dp`) and the recursive call stack.

• Memoization Table (`dp`):

• The memoization table has dimensions `n x (k + 1)`.
• The space complexity due to the memoization table is O(n * k).
• Recursive Call Stack:

• The maximum depth of the recursive call stack is `k`.
• The space complexity due to the recursive call stack is O(k).

Combining both components, the overall space complexity is O(n * k) + O(k), which simplifies to O(n * k).

In summary, the provided solution is a dynamic programming solution with memoization, resulting in a time complexity of O(n * k) and a space complexity of O(n * k). The time complexity is significantly improved compared to a naive recursive solution without memoization.

## Key Takeaways (Maximum Profit by Buying and Selling a Share at Most k Times)

• Problem Context: The problem involves maximizing stock trading profits with at most k transactions.
• Backtracking Approach: Initial solution employs backtracking, exploring all possible transactions, leading to an exponential time complexity of O(2^(n+k)).
• Dynamic Programming Optimization: Dynamic programming optimizes the solution using memoization, significantly reducing time complexity to O(n * k).
• Efficient Solution: The final solution achieves efficiency gains through dynamic programming, making it suitable for larger inputs and real-world stock trading scenarios.

#### Manraj Singh

Student at Chandigarh College of Engineering and Technology; Intern at OpenGenus.

Improved & Reviewed by:

Maximum Profit by Buying and Selling a Share at Most k Times