Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Explanation
4.
Solution Using Recursion
4.1.
Implementation in C++
4.2.
Output
4.3.
Complexity Analysis
4.3.1.
Time Complexity
4.3.2.
Space Complexity
5.
Solution Using Dynamic Programming
5.1.
Implementation in C++
5.2.
Output
5.3.
Working of the Code
5.4.
Complexity Analysis
5.4.1.
Time Complexity
5.4.2.
Space Complexity
6.
Optimized Solution Using Dynamic Programming
6.1.
Implementation in C++
6.2.
Output
6.3.
Working of the Code
6.4.
Complexity Analysis
6.4.1.
Time Complexity
6.4.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
What is dynamic programming?
7.2.
Where do we use dynamic programming?
7.3.
What do overlapping subproblems mean?
7.4.
What is a transaction?
7.5.
When does a stock transaction generate profit?
8.
Conclusion
Last Updated: Mar 27, 2024
Hard

Best Time to Buy and Sell Stock with at most K Transactions

Author Yukti Kumari
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Stocks are a great way to make profits. If you buy a stock at some price, say a, and sell it at a price, say b, then the profit is (b-a). That’s why, to make a positive profit, we wish to sell the stock at a price higher than the price we bought it for. Otherwise, it would be a loss. One whole buy + sell action is called a transaction. 

best time to buy and sell stocks

In this article, we will discuss the problem of finding the maximum profit you can achieve by buying and selling stocks based on the given constraints. 

Problem Statement

Given the stock prices of n days in an array prices, where prices[i] denotes the stock price on an ith day. You are also given an integer k. Find the maximum profit that can be achieved by completing at most k transactions. 

Also, you’re not allowed to be engaged in multiple transactions concurrently. It means you must sell the current stock before buying another.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Explanation

From the problem statement, we can infer that: 

  • We will get an array (prices) and an integer (k) as the input.
     
  • The indices of this array will denote the days, and the elements will denote the stock price on that day. 
     
  • We need to find the maximum profit from this input.
     
  • We can perform a maximum of k or less than k transactions but not more than k transactions.
     
  • We can not indulge in more than one transaction simultaneously, i.e., we must sell the current stock before buying another.
     
  • You must buy a stock before selling it.
allowed transactions

The main idea to achieve maximum profit is to buy the stock when its prices are lowest and sell it when they are highest. Before solving this problem, you must understand the “best time to buy and sell stocks 3.

Consider the example that follows to understand it better.

Example1

Input: k=2, prices = {3,5,2}

Output: 2

Explanation:

example

1st transaction: Buy the stock on day 1, and sell it on day 2. 

Profit in 1st Transaction: (5-3) = 2. 
 

No. of Transactions: 1

Maximum Profit: 2.
 

Example 2

Input: k=2, prices = {1, 4, 6, 5, 2, 3, 5}

Output: 8

Explanation: 

example

1st Transaction: Buy the stock on day 1, and sell it on day 3. 

Profit in the 1st transaction: (6-1) = 5
 

2nd transaction: Buy the stock on day 5, and sell it on day 7. 

Profit in the 2nd transaction: (5-2) = 3.
 

No. of transactions: 2
Maximum Profit: 5 + 3 = 8. 

Please try the question on “Coding Ninjas Studio” before moving on to the solution approach.

Solution Using Recursion

The following is the recursive approach to solving this problem. We will invoke a maxProfit function that returns the maximum profit from the array starting from index idx and ending at index N - 1
We will use a boolean variable "buy." If buy == true, it denotes that we have already bought a stock and now we can’t buy another until we sell it and buy == false denotes that we don’t have any current transaction in progress(that is, we may choose to buy the current stock). 

The maxProfit function will work as follows:

1. If K == 0 or idx == N, i.e. all the days are covered, or the limit of the transaction is reached.

  • Return 0


2. If buy == false, i.e. not holding any stock

  • We have two options: either buy the stock at the current price and set buy to true or not buy the current stock and call the function for the remaining array.
     
  • We make a recursive call to idx + 1 with buy marked as false. (Not holding the stock).
     
  • We make a recursive call to idx + 1 with buy marked as true and subtract prices[idx]. (Buy stock on idx-th day).
     
  • We finally return the maximum of them.


3. Else

  • We make a recursive call to idx + 1 with buy marked as true. (Hold the stock).
     
  • We make a recursive call to idx + 1 with buy marked as false and add prices[idx] and decrement K by 1. (Sell stock on the idx-th day).
     
  • Return the maximum of them.
     

Let us understand the working with the help of a state diagram

state diagram

 

Now that we understand the working of this approach, let us look at its implementation.

Implementation in C++

/*
        C++ code to find the buy and sell stocks 
        at most k times for maximum profit
*/

#include <bits/stdc++.h>
using namespace std;

int maxProfit(vector<int> &prices, int idx, int n, bool buy, int k) {
        
        // If 'k' transactions are completed
        
        if (idx == n || k == 0) {
                return 0;
        }

        // If no stock is bought
        
        if (buy == false) {
                return max(maxProfit(prices, idx + 1, n, false, k), maxProfit(prices, idx + 1, n, true, k) - prices[idx]);
        }

        // If stock is bought
        
        else {
                return max(maxProfit(prices, idx + 1, n, true, k), maxProfit(prices, idx + 1, n, false, k - 1) + prices[idx]);
        }
}

int main() {
        int n = 7;
        int k = 2;
        bool buy = false;
        vector<int> prices = {1, 4, 6, 5, 2, 3, 5};
        cout << "The maximum profit is: " << maxProfit(prices, 0, n, buy, k) << endl;
}

Output

output

Complexity Analysis

Time Complexity

O(2 ^ N) is the time complexity.

Reason: In the worst case, for every element in the array, we make two recursive calls as we have two options - either to change the state of ‘buy’ or to let it remain the same. The maximum depth of the recursion tree can go up to N.

As a result, the time complexity is O(2 ^ N).
 

Space Complexity

O(N) is the space complexity, where ‘N’ denotes the number of elements in an array.

Reason: In the worst case, the extra space used by the recursion stack can go up to a  maximum depth of N. Hence, the space complexity is O(N)

 

Now the question arises, can we optimize it further? The answer is yes, we can using dynamic programming. 

In this problem, before starting a new transaction, we’re first required to sell the last stock we bought. We can see that this problem can be broken down into smaller subproblems for each transaction. To make a profit. We need to:

  • Find a day (j) to sell the stock such that j > i and prices[j] > prices[i].
     
  • If there are multiple options for j, choose the one that maximizes the profit.
     
  • For the remaining transactions, the search space is reduced and only needs to be done from j+1 to n-1.
     

So, we can conclude that each transaction depends on its previous transaction. We can see that dynamic programming can be applied here, as the problem can be broken down into smaller subproblems for each k.

Read More - Time Complexity of Sorting Algorithms

Solution Using Dynamic Programming

The idea is to have a 2-D lookup table named dp, where dp[i][j] denotes the maximum profit from at most i transactions using prices [0...j].

Now, on any given day j, we have two options:

  • Do nothing on this day. Thus, nothing gets added to the profit.
     
  • Sell the stock. Now to sell the stock, you must have bought it on a day t=[0...j-1]. The maximum profit that can be made from this transaction is:

t:0->j-1 

Max (prices[j]-prices[t]+dp[i-1][t-1] )

where prices[j]-prices[t] is the profit from buying on day t and selling on day j. dp[i-1][t-1] is the maximum profit that can be made with at most i-1 transactions with prices[0...t-1].
 

Let’s look at the code for this approach.

Implementation in C++

/*
        C++ code to find the buy and sell stocks 
        at most k times for maximum profit using
        dynamic programming
*/

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int maxProfit(int k, vector<int>& prices) {
    
        // Number of days.
        
        int n = prices.size();
        
        /* 
            If there are 0 days
            then answer will be 0.
        */
        
        if(n==0) 
            return 0;
            
        /* 
            Declaration and initialization 
            of the dp vector.
        */
        
        vector<vector<int>> dp(k+1, vector<int>(n, 0)); 
        
        /*
            Whenever k=0, you can not make any
            transaction. Thus, no profit.
        */
        
        for(int j=0;j<n;j++) { 
            dp[0][j] = 0; 
        }

        /*
            Whenever the number of days is 0,
            the transaction is 0 and thus 
            no profit.
        */
        
        for(int i=0;i<=k;i++) {
            dp[i][0] = 0;
        }

        for(int i=1;i<=k;i++) {
            for(int j=1;j<n;j++) {
                int mx = INT_MIN; 
        /* 
            For finding the maximum profit we 
            can get by selling the stock on j
            and buying any day t<j. 
        */
        
                for(int t=0;t<j;t++) {  
                    if(t==0) { 
                        mx = max(mx,prices[j]-prices[t]);
                    }
                    else {
                        mx = max(mx,prices[j]-prices[t]+dp[i-1][t-1]);
                    }
                }

                /*
                    option 1 -> don't do anything
                    on this day.
                */
                
                int op1 = dp[i][j-1];
                
                /* 
                    option 2 -> sell the stock on 
                    this day if bought on some day t.
                */
                
                int op2 = mx;
                dp[i][j] = max(op1,op2);
            }
        }
        return dp[k][n-1];
    }

int main() {
        int k = 2;
        vector<int>prices = {1, 4, 6, 5, 2, 3, 5};
    
        int ans = maxProfit(k,prices);
        cout<<"Maximum profit in "<<k<< " transactions is: "<<ans<<endl;
        return 0;
}

Output

output

Working of the Code

Here is a detailed explanation of the working of this code:

Initialization:

  • The code first checks if there are 0 days, in which case the answer will be 0.
     
  • Then, it initializes the dp vector with k+1 rows and n columns, where k is the maximum number of transactions allowed and n is the number of days.
     
  • Next, it sets the value of dp[0][j] to 0 for all days j (as no profit can be made if no transactions are allowed) and the value of dp[i][0] to 0 for all transactions i (as no profit can be made if there is only one day).
     

Dynamic Programming:

  • The code uses a nested loop to iterate over the number of transactions i and the number of days j.
     
  • For each iteration, it finds the maximum profit that can be made by selling the stock on day j and buying on any day t (0 <= t < j).
     
  • Then, it calculates two options:

    • Option 1: Not selling the stock on day j. The maximum profit in this case will be equal to the maximum profit of the previous day j-1.
       
    • Option 2: Selling the stock on day j. The maximum profit in this case will be equal to the maximum of all profits made by selling on day j and buying on day t, plus the profit made by i-1 transactions till day t-1.
       
  • The code updates the dp vector with the maximum of the two options.
     

Output:

Finally, the code returns the maximum profit that can be made for k transactions on n days, which is stored in dp[k][n-1]

Complexity Analysis

Time Complexity

O(n*n*k) is the time complexity, where n is the number of days and k is the number of the maximum transaction possible.

Reason: Because we’re iterating all the i’s from 1 to k and then all the j from 0 to n. This nested for loop will have O(n*k) time complexity. Also, for each j, we’re iterating through all the t from 0 to j-1, which again has a complexity of O(n). Thus, the overall complexity will be O(n*n*k).
 

Space Complexity

O(n*k) is the space complexity, where n is the number of days and k is the maximum number of transactions possible. 

Reason: We are using auxiliary space in storing the dp vector of size n*k.

 

We can further optimize this time complexity. The next approach also employs dynamic programming, but it is optimized to O(n*k).

Also check out - Rod Cutting Problem

Optimized Solution Using Dynamic Programming

The optimized dynamic programming approach for the best time to buy and sell stocks in at most k transactions can be implemented as follows:

  • Initialize a 2-D dp vector with k+1 rows and n columns, where n is the number of days.
     
  • Initialize dp[0][j] as 0 for all j because if no transactions are allowed, the profit will be 0.
     
  • Initialize dp[i][0] as 0 for all i because if there is only one day, no transactions can be made.
     
  • In each iteration i, set the initial value of mx as -prices[0]. This is because, for j = 1, only 0 is the day left, and dp[i-1][t-1] for t == 0 will be 0. Therefore, dp[i-1][t-1] -prices[0] = 0-prices[0] = -prices[0].
     
  • For each day j, calculate the maximum profit in two ways:

    • Do not do anything on this day, which is represented by dp[i][j-1].
       
    • Sell the stock on this day if bought on some day t, which is represented by prices[j]+mx.
       
  • Take the maximum of these two options and store it in dp[i][j].
     
  • Keep updating the value of mx as max(mx, dp[i-1][j-1]-prices[j]) in each iteration.
     
  • The final answer will be stored in dp[k][n-1], where k is the maximum number of transactions allowed, and n is the number of days. 
     

Below is the code for the above-discussed approach.

Implementation in C++

/*
        C++ code to find the buy and sell stocks 
        at most k times for maximum profit using
        dynamic programming optimized version.
*/

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int maxProfit(int k, vector<int>& prices) {
    
        // number of days
        
        int n = prices.size();
        
        /* 
            if there are 0 days 
            then answer will be 0.
        */
        
        if(n==0) {
            return 0;
        }

        /* 
            Declaration and initialization 
            of the dp vector.
        */
        
        vector<vector<int>> dp(k+1, vector<int>(n, 0));

        /* 
            Whenever k=0, you can make any
            transaction. Thus no profit.
        */
        
        for(int j=0;j<n;j++) {
            dp[0][j] = 0;
        }

        /* 
            Whenever the number of days is 0, 
            the transaction is 0, and thus 
            no profit.
        */
        
        for(int i=0;i<=k;i++) {
            dp[i][0] = 0;
        }
        for(int i=1;i<=k;i++) {

             // Set mx initially to -prices[0].
             
            int mx = -prices[0];
            for(int j=1;j<n;j++) {


                /*
                    option 1 -> don't do
                    anything on this day
                */
                
                int op1 = dp[i][j-1];


                /* 
                    option 2 -> sell the stock 
                    on this day if bought on 
                    some day t.
                */
                
                int op2 = prices[j]+mx;
                dp[i][j] = max(op1,op2);
                
                // Keep updating mx every time.
                
                mx = max(mx,dp[i-1][j-1]-prices[j]);
            }
        }
        return dp[k][n-1];
}


int main() {
        int k = 2;
        vector<int>prices = {1, 4, 6, 5, 2, 3, 5};
    
        int ans = maxProfit(k,prices);
        cout<<"Maximum profit in "<<k<< " transactions is: "<<ans<<endl;
        return 0;
}

Output

output

Working of the Code

The code for finding the maximum profit from buying and selling stocks at most k times using dynamic programming optimized version can be explained as follows:

Input and Initialization:

  • The input to the code is an integer "k" that represents the maximum number of transactions allowed, and a vector of prices of stocks.
     
  • The number of days is calculated by finding the size of the prices vector.
     
  • If there are 0 days, then the answer will be 0.
     
  • The dp vector is declared and initialized with the size of k+1 rows and n columns, where n is the number of days.
     
  • The values of dp[0][j] are initialized to 0 for all j, as no profit can be made if no transactions are allowed.
     
  • The values of dp[i][0] are initialized to 0 for all i, as no profit can be made if there are no days.
     

Dynamic Programming:

  • The code iterates over the number of transactions (i) and days (j).
     
  • For each iteration, two options are calculated:

    • Option 1: Not making any transaction on this day.
       
    • Option 2: Selling the stock on this day if bought on some day t.
       
  • The maximum of the two options is stored in the dp[i][j] for each iteration.
     
  • A variable "mx" is used to keep track of the maximum profit that can be made from selling stocks bought on some day t. This value is updated every time.
     

Output:

The code returns the value of dp[k][n-1], which represents the maximum profit that can be made from the last day, given the maximum number of transactions allowed.

Complexity Analysis

Time Complexity

O(n*k) is the time complexity, where n is the number of days and k is the maximum number of transactions possible. 

Reason: It is because we’re iterating all the i’s from 1 to k, and then for all j from 0 to n. This nested for loop will have O(n*k) time complexity. 
 

Space Complexity

O(n*k) is the space complexity, where n is the number of days and k is the maximum number of transactions possible. 

Reason: We are using auxiliary space in storing the dp vector of size n*k.

Check out Longest Common Substring

Let us now answer some of the frequently asked questions.

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is an optimization method used in various programming problems. We use it to memorize the results so that they can be used later when needed.

Where do we use dynamic programming?

Dynamic programming is used in problems where the solution depends on smaller, overlapping subproblems.

What do overlapping subproblems mean?

A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times

What is a transaction?

A complete buying and selling action is called a "transaction." 

When does a stock transaction generate profit?

When you sell the stock at a price that is higher than the price at which you bought it, the stock transaction gives you a profit.

Conclusion

In this article, we’ve discussed the problem of “best time to buy and sell a stock” in at most k transactions. We have covered the solutions using recursion and dynamic programming

You can refer to the following articles for more such problems.

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparation, and so much more!

Happy Learning, Ninjas!

Previous article
Best Time to Buy and Sell Stock III
Next article
Best Time to Buy and Sell Stock with Cooldown
Live masterclass