Do you think IIT Guwahati certified course can help you in your career?
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.
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.
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.
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:
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:
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 fromindex 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.
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;
}
You can also try this code with Online C++ Compiler
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.
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;
}
You can also try this code with Online C++ Compiler
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).
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;
}
You can also try this code with Online C++ Compiler
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.
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.
85+ registered