Redirecting to
NADOS


  Prev   Next

Buy and Sell Stocks- K Transactions Allowed







I will tell you how to become rich. Close the doors. Be fearful when others are greedy. Be greedy when others are fearful.
~ Warren Buffett

Buy and Sell Stocks- K Transactions Allowed

Welcome back, dear reader. So, this is the last problem of Dynamic Programming as well as the stock sell and buy problems series. Hope you have solved the previous 5 problems of this series. Let's now move to the 6th one.

Important Links : Problem Link, Solution Video

Problem Discussion :

Here, we are given an input n representing the numbers of days and we are given n values representing the price of stocks on each day. We are also given k which represents the number of transactions allowed. We have to find the maximum profit that can be made in n days with k transactions allowed. Also, there is a condition that there should not be any overlapping transactions. This means that we can not buy another stock before selling the previous one.

You may refer to the BUY AND SELL STOCKS WITH K TRANSACTIONS video to understand the question clearly if you have any doubts regarding it. We recommend you solve the question on your own first. We also recommend you to watch the solution video even if you have solved the problem as it will give you a lot of insight into the question.

Method-1:
Approach :
  1. Storage and Meaning: We will take a 2-D matrix dp[k+1][n] where k is the number of transactions and n is the number of days.
    img
    As shown in the diagram, we will make a matrix of size (k+1)xn. Each element (dp[i][j]) of this matrix will represent the maximum profit that can be made if 'i' transactions are allowed to take place till 'j' days.
    The first row of the matrix represents that the number of transactions is zero. Since the number of transactions is zero, we cannot make a profit if we are given infinite days. Also, the first column represents that the number of days given to us is 0. This means that we have to buy and sell the stock on the same day. Since the price of the stock does not change on the same day, we cannot extract any profit. So, in this case, also, all the values should be 0.
    Now, the rest of the values of the matrix can be filled as follow:
    1. Since dp[i][j] represents the max profit that can be obtained if 'i' transactions can be carried out in 'j' days, all the transactions must be completed before the 'j th' day.
    2. So, we can find out the max profit for that case. Also, transactions could take place on different days. So, we will compare all possible cases of the transactions on and before the jth day and find that transaction which gives us the max profit.
    Have a look at the diagram given below:
    img
    As already explained, we have first filled the first row and the first column with all 0 values. Now, we will start filling the matrix from dp[1][1].
    Since dp[1][1] represents that one transaction is allowed till day 1, we can either have that transaction on the 0th day i.e. the transaction will be b0s0 meaning buying and selling the stock on 0thday. Else, there can be a transaction between 0th day and 1st day . So, the transaction will be b0s1 i.e. buy on day 0 and sell on day 1. But, the price of the stock is greater on day 0 than on day 1. So, we will not perform this transaction as it will be a case of loss. So, the only transaction remaining is the transaction b0s0 and this will become our transaction of max profit. So, at dp[1][1] we will store 0 i.e the max profit that we got from the transaction b0s0.
    Now, dp[1][2] means we can complete 1 transaction till day 2. Now, this can be done in various ways. Either we complete the transaction on day 0 only, which will give us the max profit=0 (buying and selling on day 0). The other way is that we can have a transaction between day 2 and day 1 which means that we buy the stock on day1 and sell it on day 2. So, the transaction will be b1s2 and the max profit will be 1 in this case as the stock has a price higher than 1 on day 2 as compared to day 1. The other way can also be to have a transaction between day 2 and day 0 meaning buying on day 0 and selling on day 2. Since the price on day 1 is greater than the price on day 2, this transaction will not be carried. So, we will store the max profit from transaction s1b2 i.e max profit=1 in dp[1][2].
    Similarly, we can store the values in the entire matrix. You may refer to the solution video to understand the above diagram and complete the procedure of storing the data inside this matrix.
  2. Traverse and Solve: Wait what are you wondering? Where's the direction of the solving step? Well, if you didn't catch up to that, we have already discussed the entire concept of small and bigger problems. So, we know what each element is and what row 0 and column 0 represent. Thus, we know that dp[0][0] is the smaller problem and we have to solve the matrix from here till the end of the matrix only. This is the direction concept which we already covered in the storage and meaning step. Well, you would have also noticed that in the storage and meaning concept, we have discussed everything. We also know the procedure of solving this problem but not in terms of coding. So, let's try to understand that:
    1. See, we have stored at dp[i][j] the max profit when i transactions are allowed till j days. So, in dp[i][j-1] we have max profit if i transactions are allowed till j-1 days. So, i transactions might get completed before j days. So, we can have dp[i][j-1] as a potential answer for the max profit at dp[i][j]. You may refer to the solution video to understand this point in a better way and get the concept fully.
    2. Also, if the i transactions were not complete until j-1 days, then those transactions can give us max profit depending upon which day they are carried out. So, we will also have all the transactions over all previous days from j as the potential answers. They are actually from dp[i-1][j] to dp[0][0]. Why? Think about it!!! You may refer to the solution video to understand this point in a better way.

So, now that we know all the three steps in dynamic programming, let's jump into the code. Dear reader, we suggest you first watch the video to understand the code easily and then try to code it yourself to get a better grasp of the concept.

Pseudo Code
  1. Storage and Meaning: We will make a 2-D array of order k X n where k is the number of transactions=number of rows and n is the number of days=number of columns. Each element in this matrix specifies the max profit that can be obtained if i transactions are performed in j days.
  2. The direction of Solving: The first row of the matrix represents that the number of transactions is 0 and the first column represents that there are 0 days. So, dp[0][0] is the smallest problem i.e. max profit obtained by 0 transactions in 0 days. So, we will move in the direction from dp[0][0] to dp[k][n] to solve this problem.
  3. Traverse and Solve: We are going to traverse in this array from the decided direction and we will compare all possibilities of transactions till a particular day and fill dp[i][j] with the max profit. How will we do this? Think about it!!! We will discuss this in the explanation part.
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner scn=new Scanner(System.in); int n=scn.nextInt(); int[] arr=new int[n]; for(int i=0;i< n;i++) { arr[i]=scn.nextInt(); } int k=scn.nextInt(); int[][]dp=new int[k+1][n]; for(int t=1;t<=k;t++) { for(int d=1;d< arr.length;d++) { int max=dp[t][d-1]; for(int pd=0;pd< d;pd++) { int ptilltm1=dp[t-1][pd]; int ptth=arr[d]-arr[pd]; if(ptilltm1+ptth>max) { max=ptilltm1+ptth; } } dp[t][d]=max; } } System.out.println(dp[k][n-1]); } }
java; true";
Analysis

Let us analyze the time and space complexity of the above code

Time Complexity :

We have three nested loops. So, we have an idea that the time complexity will be cubical. Now, let us analyze the matrix.

img

The O(kxn) is from the traversal of the matrix and the extra n comes from traversing the previous row elements to compare for the max profit. Now, we are not traversing the entire row every time but the max we are doing is we are traversing a row completely which has n columns. So, this extra power of n makes the time complexity cubical and equal to O(kxn2).

SPACE COMPLEXITY :

Well, this is simple to discuss. It will be O(kxn) as we took a matrix of size dp[k+1][n].

Optimization Method:
Approach :

As discussed above, the time complexity is cubical because of comparing the previous row values for calculating the max profit. So, we will try to reduce the innermost loop. Look at the diagram given below:

img

The above diagram shows that for calculating the value of v23 we are applying the innermost loop which compares the three quantities written at the right in the diagram. So, if we look carefully, we can notice that p3 is common in all of these. So, the above terms can just be rearranged as follows:

img

Since p3 is common, we realize that we just have to find the max between all these terms without considering p3. If we again look at the equations carefully, we realize that we are subtracting from the value vij its own column values.

Soo, now it doesn't seem like a big task, does it? We can easily remove the third loop by finding the max among all these values while traversing only. How? Look at the code given below:

Pseudo Code

The method is the same as above. We will just reduce the innermost loop in the above code. This will be done by finding the max value while traversing the matrix only. Have a look at the explanation below to understand this in depth.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner scn=new Scanner(System.in); int n=scn.nextInt(); int[] arr=new int[n]; for(int i=0;i< n;i++) { arr[i]=scn.nextInt(); } int k=scn.nextInt(); int[][]dp=new int[k+1][n]; for(int t=1;t<=k;t++) { int max=Integer.MIN_VALUE; for(int d=1;d< arr.length;d++) { if(dp[t-1][d-1]-arr[d-1]>max) { max=dp[t-1][d-1]-arr[d-1]; } if(max+arr[d]>dp[t][d-1]) { dp[t][d]=max+arr[d]; } else { dp[t][d]=dp[t][d-1]; } } } System.out.println(dp[k][n-1]); } }
java; true";

What we did is that we did not run a loop, rather we first found out the value of max of all those values while filling the array and later added the value of last column to it to compare it to dp[i][j-1]. If you have any problem understanding the above code and concept, refer to the solution video to understand the above procedure and code completely.

Analysis
Time Complexity :

Now that we have avoided the use of the innermost loop, we have the time complexity as O(kxn) where k is the number of transactions allowed and n is the number of days.

SPACE COMPLEXITY :

We have not done any reduction in the space, so the space complexity remains the same i.e. O(kxn).

So dear reader, did you get the solution and the optimization? We know this can be a little hard to understand so we request you to watch the complete solution video once. It will be the most effective solution for you to understand this problem.

Suggestions:

Dear reader, here are some suggestions from our side that you don't want to miss:

  1. This problem is hard to understand in one go. We suggest you watch the complete solution video once and then take a break or solve another problem, then come back to this question and try to remember whatever you learned in the video once. Then watch the video again. This way, you'll get a good grasp of every concept taught in the video.
  2. With this question, we have come to an end of our problems on dynamic programming. So, we request you to revise this section and keep revising it as you need to be good at it. We'll solve more problems on dynamic programming in level-2. So, till then keep revising all that you have studied before moving on to the next topic. Till then, Happy Coding!!!
Functions and arrays
Dynamic Programming (Tabulation)
Author: Guneet Malhotra
 
Run
Id Name