Dear reader, welcome to the article on the problem named 'Buy And Sell Stocks With Transaction Fee - Infinite Transactions Allowed'. It is the 3rd problem in the series Buy & Sell Stock.
Important Links : Problem Link, Solution Video
Buy And Sell Stocks With Transaction Fee
Learning to code is useful no matter what your career ambitions are.
~ Arianna Huffington
Dear reader, welcome to the article on the problem named 'Buy And Sell Stocks With Transaction Fee - Infinite Transactions Allowed'. It is the 3rd problem in the series Buy & Sell Stock.
Important Links : Problem Link, Solution Video
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,3,2,8,4,9]. The maximum profit can be achieved by:
- Buying at day 0 = 1
- Selling at day 3 = 8
- Buying at day 4 = 4
- Selling at day 5 = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
We are discussing a very classic dynamic programming based approach. We will maintain 2 states for each day.
Can you derive a relation for the states at day i, using the values of bsp state and ssp state at day i-1?
BSP State: If it is necessary to have one stock extra in our hand, then we have to two options:
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 will consider that option whichever gives us more profit (or less loss).
The only task left is to analyze the corner case.
Note: Please note that there can be negative value in bsp, or ssp 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.
Please note that 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.
Some Modifications in the logic to reduce Space Complexity
Uptil now, we have used two 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 i^{th} 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 4 integer variables, two for previous day bsp and ssp state, namely bstp and sstp , and other two variables for the current day bsp and ssp state, namely nbstp and nsstp.
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.
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.
O(N)
Since, we are traversing through the array of n integers (representing days), and filling 2 states for each day, the time complexity will be O(2 * N) = O(N).
O(1)
Since we have replaced our logic of two arrays with just 4 integer variables, the space complexity will reduce from O(N) to O(1).
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 ?
Along with the maximum profit, we can also maintain a string (or an array) of the current bsp and ssp 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 - Transaction Fee - Infinite Transactions Allowed'. Next problem will be the 4th problem in this series 'Buy And Sell Stock - Cooldown - Infinite 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.