Dear reader, welcome to the article on the problem named "Buy And Sell Stocks with Cooldown - Infinite Transactions Allowed". It is the 4th problem in the series Buy & Sell Stock.
Important Links : Problem Link, Solution Video
Prev Next
Buy & Sell Stock - Cooldown
When you throw yourself out there great things happen. Just take this course blindly and dive into the world of programming starting from scratch.
~ Prajwal A.
Buy & Sell Stock - Cooldown
Problem Discussion :
- You are given an array of n elements. Element at index i represents a stock value on ith day.
- You are required to print the maximum profit you can make if you are allowed infinite transactions, but we have a cooldown period for 1 day between selling stock and buying new stock.
- It means that if we had sold a stock yesterday, then we cannot buy the new stock today, we will have to remain in a cooldown state for 1 day and hence can buy new stock tomorrow (or any day after tomorrow) only.
- Hence, you cannot buy on the next day after you sell, you have to cooldown for a day at-least before buying again.
Note - There can be no overlapping transaction. One transaction needs to be closed (a buy followed by a sell) before opening another transaction (another buy). We cannot first buy 2 stocks and then sell them, i.e. states like "BBSS" are not allowed
Nobody will laugh at you, if you didn't know this! It is very trivial, but still, I want to let you know that you cannot sell a stock before buying it! You cannot have a state "SB".
Example:
Consider the array of days as : [1,2,3,0,2].
The maximum profit can be achieved by:
- Buying at day 0 = 1
- Selling at day 1 = 2
- Cooldown for day 2
- Buying at day 4 = 0
- Selling at day 5 = 2
Hence the profit = ((2 - 1) + (2 - 0)) = 3.
Approach :
This problem is very similar to the previous problem where instead of cooldown, we had to take transaction fees into consideration. Here, we will need to maintain 3 states for each day.
- For any day, the first state will be the maximum profit we can make if there is one stock left to be sold. This state does not necessarily require you to buy the stock at the current day. It just requires that there is one stock extra, i.e. the number of stocks bought should be one more than the number of stocks sold so far. Also, we need to keep in mind that before buying any stock, we have to maintain a cooldown of 1 day with the day when the last stock was sold.
- The second state will be the maximum profit we can make if we have no stock available to sell. This state does not necessarily require you to sell the stock at the current day. It just requires that the number of stocks bought should be equal to the number of stocks sold so far. We need not account for the cooldown period of the last stock bought in this state, as we will maintain a 3rd state for cooldown.
- The third state will be the maximum profit we can make if we have no stock available to sell. This state will be similar to the second state, but there is one extra requirement, that we must have completed the cooldown (of 1 day) after the selling of the last stock.
- Let us name the first state as bsp (bought state profit), the second state as ssp (sold state profit) and third state as csp (cooldown state profit). We will create three arrays, one for each state, of size equal to the number of days.
Can you derive a relation for the states at day i, using the values of bsp state, ssp state and csp state at day i-1?
BSP State: If it is necessary to have one stock extra in our hand, then we have two options:
- We can use the csp state of previous day and buy the stock at current day, i.e. take the maximum profit upto previous day (with cooldown period completed) and buy the stock at current day.
Q) Why we cannot take the maximum profit upto previous day from bsp state?
R) This is because if we consider the previous day, which already has one stock extra, then buying on the current day will make two stocks extra. But we are not allowed such transactions, as we must sell stock before buying it again. Q) Why we cannot take the maximum profit upto previous day from ssp state?
R) This is because if we consider the ssp state, then we have not completed the cooldown after the last stock sold. Buying the stock at current day without completing the cooldown is not allowed. - We do not buy on the current day, but instead use the previous bsp state, i.e. we can take the maximum profit with one stock left upto previous day only. This will make us left with one stock extra only, as we are not buying or selling today.
We will consider that option whichever gives us more profit (or less loss).
SSP State: If it is necessary to have to equal number of stocks bought and sold, then we have two options:
- We take the bsp state of the previous day and sell that extra stock which was left in the previous day's state today. Hence, now, we will be left with no extra stocks in our hand, i.e. the number of stocks bought and sold will become extra.
Q) Why can't we take the ssp state (or csp state) of the previous day and sell a stock today?
R) Since ssp state (or csp state) means we do not have any extra stock in our hand, we cannot sell a stock without even buying it first. A state like "SB" is not possible. - We take the ssp state of the previous day as it is, and do not buy or sell stock today. Hence, ssp state of previous day, which gives the maximum profit with no stocks left upto previous day will become the maximum profit with no stock left upto the current day.
We will consider that option whichever gives us more profit (or less loss).
CSP State: If it is necessary to have to equal number of stocks bought and sold, and we have completed a cooldown of 1 day, then we have two options:
- We take the ssp state of the previous day and rest today, i.e. let today be the cooldown period. Hence, now, we will have equal stocks bought and sold, and we would have completed the cooldown period.
Q) Why can't we take the bsp state of the previous day and cooldown today?
R) We need to cooldown only after a complete transaction, i.e. after selling a stock and before buying a new stock. Hence, taking into account the bsp state of the previous day does not make sense, as we need not cooldown between buying a stock and selling that same stock. - We take the csp state of the previous day as it is, and do not buy or sell stock or cooldown today. Hence, csp state of previous day, which gives the maximum profit with no stocks left upto previous day (with cooldown completed) will become the maximum profit with no stock left upto the current day (with cooldown completed).
We will consider that option whichever gives us more profit (or less loss).
The only task left is to analyze the corner case.
- It is the first day, when we will not have any previous day.
- In this case, for the bsp state, we must have to buy the stock at the current day as option 2 is not available.
- For the ssp state, we do not have any option to sell stock, hence the maximum profit will be 0 (no stocks bought, no stocks sold).
- For the csp state, we do not have any previous ssp state, and since there is no complete transaction, we have nothing to cooldown. Thus, maximum profit will be 0 in this case also (no stocks bought, no stocks sold and no cooldown completed).
Note: Please note that there can be negative value in any state, which represents we are at a loss. (Profit of -x is equivalent to loss of x).
At last, we will return the value of ssp state of the last day as our result, since it will contain the maximum profit with no extra stock left in our hand (no incomplete transaction) and it has taken into account all the n days.
Q) Why cannot we consider the bsp state of the last day as our result?
R)The bsp state of the last day cannot be considered as our result, because it has one incomplete transaction, because there is one stock extra in our hand, which is still left to be sold.
Q) Why cannot we consider the csp state of the last day as our result?
R) Please note that we need to cooldown only between selling a stock which we bought previously and buying a new stock. Thus, we need not cooldown after the last stock sold. Did you get the point of "Why to unnecessarily add one day of cooldown"?
Pseudo Code
- Create three arrays of size = n, named bsp, ssp and csp respectively.
- Initialize bsp[0] as - arr[0] (bought the stock at day 0, hence in loss of arr[0], or in profit of -arr[0]).
- Initialize ssp[0] and csp[0] as 0 (no stocks bought or sold).
-
Now loop from index/day 1 to n-1, and Update the bsp & ssp states as given:
- bsp[i] = max ( csp[i - 1] - arr[i], bsp[i - 1] )
- ssp[i] = max ( bsp[i - 1] + arr[i], ssp[i - 1] );
- csp[i] = max( ssp[i - 1], csp[i] );
- Return the value of ssp[n-1] as the maximum profit with infinite transactions allowed.
Some Modifications in the logic to reduce Space Complexity
Uptil now, we have used three arrays of size n each. But, you can easily see that there is no need to store the states of all the previous days for the calculations. We just need the state of the immediate previous day ( (i - 1)th previous day for ith current day) and all the days before (i-1), i.e. days (i-2), (i-3), and so on, need not be stored.
Hence, we can replace our logic with 6 integer variables, three for previous day bsp, ssp and csp state, namely bstp, sstp and cstp , and other three variables for the current day bsp, ssp and csp state, namely nbstp, nsstp and ncstp.
Well, there will be a little difference in the implementation part, but, I expect from you that you can easily make these amendments accordingly.
Note: Before reading the Code, we recommend that you must try to come up with the solution on your own. Now, hoping that you have tried by yourself, here is the Java code.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int bstp = -arr[0];
int sstp = 0;
int cstp = 0;
for(int i = 1; i < arr.length; i++){
int nbstp = 0;
int nsstp = 0;
int ncstp = 0;
if(cstp - arr[i] > bstp){
nbstp = cstp - arr[i];
} else {
nbstp = bstp;
}
if(bstp + arr[i] > sstp){
nsstp = bstp + arr[i];
} else {
nsstp = sstp;
}
if(sstp > cstp){
ncstp = sstp;
} else {
ncstp = cstp;
}
bstp = nbstp;
sstp = nsstp;
cstp = ncstp;
}
System.out.println(Math.max(sstp, cstp));
}
}
java;
true";
Java Code is written and explained by our team in the solution video.
Dry Run of the code using an example is taken and elaborated in the same video.
Analysis
Time Complexity :
O(N)
Since, we are traversing through the array of n integers (representing days), and filling 3 states for each element, the time complexity will be O(3 * N) = O(N).
SPACE COMPLEXITY :
O(1)
Since we have replaced our logic of two arrays with just 6 integer variables, the space complexity will reduce from O(N) to O(1).
Follow Up:
Q) If someone asks you to print the state in which you get the maximum profit, i.e. the sequence of the days in which stocks were bought and sold, then will you be able to adapt according to the problem requirements ?
R) Along with the maximum profit, we can also maintain a string (or an array) of the current bsp, ssp and csp state, the string will represent the sequence of stocks buy and sell upto the current day. Finally, we will print the resultant sequence which is stored in the ssp state of the last day.
Hope that you liked the article on "Buy And Sell Stock - with Cooldown - Infinite Transactions Allowed".
We have solved three problems on infinite transactions:
- Infinite Transactions with No Transaction Fee and No Cooldown
- Infinite Transactions with Transaction Fee, but No Cooldown
- Infinite Transactions with Cooldown, but No Transaction Fee
What Next? I should tell you that the next problem is not Infinite transactions with both transaction fee and cooldown. (It is very easy to club the questions).
Next problem will be the 5th problem in this series "Buy And Sell Stock - Two Transactions Allowed".
Subscribe to Pepcoding's youtube channel for more such amazing content on Data Structures & Algorithms and follow the resources available for all students in the resources section of Pepcoding's website.
You can suggest any improvements to the article on our telegram channel, or on the youtube channel's comment section.
