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

Yukti Kumari
Last Updated: May 13, 2022

Introduction

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

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 price of the stock at day i and an integer k, find the maximum profit you can achieve by completing at most k transactions. 

NOTE: You’re not allowed to be engaged in more than one transaction at the same time. It means you must sell the stock before buying again.  

For example: 

INPUT : k = 2, price = [2,4,1]

OUTPUT :  2

Buying on day 1 (at a price 2) and selling on day 2 (at a price 4) will give the maximum profit of (4-2) = 2. 

INPUT : k = 2, price = [3,2,6,5,0,3]

OUTPUT :  7

Buy on day 2 and sell on day 3 -> profit = (6-2) = 4

Then, buy on day 5 and sell on day 6 -> profit = (3-0) = 3.

So the maximum profit will be 4+3 = 7.

Recommended: Please try it on “CodeStudio” before moving on to the solution approach.

Approach - 1  Using Recursion

  1. We will call 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: 
  2. If K == 0 or  idx == N
    • Return 0
  3. If buy == false, 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
  4. Else
    • We make a recursive call to idx + 1 with buy marked as true. (Hold the stock).
    • We make a recursive call to idx + 1with 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 mechanism with the help of a state diagram

 

C++ Implementation

/* 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 = 6;
    int k = 2;
    bool buy = false;
    vector<int> prices = {326503};

    cout << "The maximum profit is: " << maxProfit(prices, 0, n, buy, k) << endl;
}

 

Output-

The maximum profit is: 7

Time Complexity - O(2^N)

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. Hence the time complexity is O(2 ^ N).

Space Complexity - O(N)

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

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)

Can we optimize it further?

Yes. Let’s see how in the next section.

In this problem, before starting a new transaction, we’re first required to sell the last stock we bought. Now let’s assume that we buy a stock on day i. To sell this stock, we need to find a day j, such that j>i and prices[j]>prices[i]. In this way only, we can make a profit. Now let’s assume that there are many such j’s. So the question is which one should we choose? Now see that if we decide one such j, then for the next k-1 left transactions, we have reduced our search space to 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.

Approach 2: 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 day j, we have two options:

  • Do nothing on this day. Thus nothing gets added to the profit.
  • Sell the stock. Now in order to sell the stock, you must have bought it on a day t=[0...j-1] . 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 prices[0..t-1].

 

Steps are: 

  • If the number of days is 0, then the answer is 0 because no transaction can be made.
  • Now, define the 2-D dp vector of size (k+1)*(n) and initialize all the values in it to 0.
  • Base cases:
    • Whenever k=0, you can make any transaction. Thus no profit. Hence for all j from 0 to n-1, such that k=0, dp[0][j] = 0.
    • Whenever the number of days is 0, the transaction is 0 and thus no profit. In this case also, for all i from 0 to k, dp[i][0] = 0.
  • Now for each transaction from 1 to k, we’ll compute for each j from 1 to n-1, the value of dp[i][j]. As said earlier, for each j, there are two options. 
    • If we do nothing, option1 = dp[i][j-1]. Because the number of transactions remains the same and the number of days left is 0 to j-1.
    • If we sell the stock, we need to find the maximum profit that can be made from any t from 0 to j-1, such that we bought the stock on day “t”. Thus, option2 =  t:0->j-1 max(prices[j]-prices[t]+dp[i-1][t-1]) . We run a loop from o to j-1 and find this maximum. 
  • Dp[i][j] will be max(option1, option2).
  • In the end we return dp[k][n-1].

 

Below is the implementation of this approach.

#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 dp vector
        vector<vector<int>> dp(k+1vector<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++){
            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){ 

                        // if t==0, dp[i-1][t-1] doesn't makes sense
                        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 buy if bought  //on some day t.
                int op2 = mx;
                dp[i][j] = max(op1,op2);
            }
        }
        return dp[k][n-1];
    }

int main(){
    int n,k;
    cin>>n>>k;
    vector<int>prices(n);
    for(int i=0;i<n;i++){
        cin>>prices[i];
    }
    int ans = maxProfit(k,prices);
    cout<<ans<<endl;
    return 0;
}

Input

n=2, k=2, prices = [3,2,6,5,0,3]

Output

7

 

Time complexity - O(n*n*k)

O(n*n*k), 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 for all 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 O(n). Thus overall complexity will be O(n*n*k).

Space complexity- O(n*k)

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

Reason: Because we’re storing the size of dp vector is n*k.

Approach 3: Using Dynamic Programming but optimized to O(n*k)

In the previous approach, finding the suitable t to find the “mx” value cost us another O(n) time.In order to reduce the time complexity to O(nk), we must find t:0->j-1 max(prices[j]-prices[t]+dp[i-1][t-1]) this expression in constant time. If we see carefully, t:0->j-1 max(prices[j]-prices[t]+dp[i-1][t-1]) is same as prices[j] + t:0->j-1 max(dp[i-1][t-1]-prices[t]).

Second part of the above expression mx = t:0->j-1 max(dp[i-1][t-1]-prices[t]) can be included in the dp loop by keeping track of the maximum value till j-1.

Steps are the same as in the previous approach. The only change is in the place of that for loop for finding the mx value, we are keeping the mx value till j-1 and update it every time. Also, for each i, the initial value of mx will be -prices[0] 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]. 

Below is the code for the above-discussed approach.

#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 dp vector
        vector<vector<int>> dp(k+1vector<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 buy //if bought on some day t.
                int op2 = prices[j]+mx;
                dp[i][j] = max(op1,op2);

                // Keep updating mx everytime
                mx = max(mx,dp[i-1][j-1]-prices[j]);
            }
        }
        return dp[k][n-1];
}

int main(){
    int n,k;
    cin>>n>>k;
    vector<int>prices(n);
    for(int i=0;i<n;i++){
        cin>>prices[i];
    }
    int ans = maxProfit(k,prices);
    cout<<ans<<endl;
    return 0;
}

 

Input

n=2, k=2, prices = [3,2,6,5,0,3]

Output

7

Time complexity- O(n*k)

O(n*k), 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 for all j from 0 to n. This nested for loop will have O(n*k) time complexity. 

Space complexity- O(n*k)

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

Reason: Because we’re storing the size of dp vector is n*k.

Frequently asked questions

1. What is dynamic programming, and where is it used?

Answer: Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

2.  What are overlapping subproblems?

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

3.  Where can I submit my “Best time to buy and sell stock” code?

Answer: You can submit your code on CodeStudio and get it accepted here right away.

4.  When does a stock transaction give profit?

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

5. Are there more Data Structures and Algorithms problems in CodeStudio?

Answer: Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key takeaways

In this article, we’ve discussed the best time to buy and sell stock problem. There are various problems similar to this such as Best time to buy and sellBuy and sell stockSelling stock, and Buy and sell stock - III. I would suggest you solve them to gain more confidence in these kinds of problems. These questions are asked during various coding contests as well as placements tests and thus are very important. 

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!
 

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think