Transcript

Hello everyone likes Tara songs from Niko today. So today we have this problem called Best time to buy and sell stock too. There was an earlier version also of this problem. And in that problem we actually could only buy the stock once and sell it once throughout the entire given time period. But here we have a little bit more flexibility in buying and selling. Let's look at the description. You are given an integer array prices where prices I is the price of a given stock on the 8th day. So basically there is some. Random stock may be an Apple Store, Google stock, whatever it is, and we are given a list of prices of that stock on different days. So on the first day the price is set in, the next day is 1, the next day is five. Then in the same way we have 3-6 and four for different days. On each day you may decide to buy or sell the stock. You can only hold at most one share of the stock at any time. So basically I cannot say that OK, give me two quantity of this share for this talk. I can only buy one share of the stock at any given time. OK, fine. However, you can buy it and then immediately sell it on the same day. So it means I can do day trading, I can buy it and definitely sell it on the same day immediately. So we need to find and return the maximum profit we can make during the entire time. OK, fine. So let's take an example of this one. And these kind of problems are best visualized with the help of a graph. So here we have the graph for this particular example. Here. On the first year the price is 7, as you can see here. On the next year the price is 1. Then the next is the price is five, then three, six and four. Now we have to figure out the maximum profit that we can achieve. OK, fine, we can actually start from. The seven because that is the day one. So I will have to see where the seven is going. Is it on the back line or is it on the incline? That is the question right now. So here we can simply see that OK, if I buy on 7 the next day the price is going 1. So if I buy on 7:00 and 7:00 on the next day, I am going on a downward trend. I am going to basically lose the money. But if I buy on the second day that is here, then I'm actually basically. An uptrend, I can sell on this day and make a profit. So basically in this example or in this scenario, we actually can predict the future. If I'm on the seven, I can see if on the next day I'm going to make profit or loss depending on the next day's price. So basically I can spot the prints. I can see that from here to here I'm going to make a loss, and then on the next day I'm going to make a profit. From here to here, then again I'm going to make a loss. Right, so basically what I need to do is I need to buy on this particular point. Let me change the color. I need to buy here, I need to buy here, I need to sell here, and then again I have to buy here and then I need to sell here. Now, how am I going to figure out whether I should buy at this point or not? Simple, right? I need to check whether the next day's price, that is, this price, is greater than this price or not. And I can check it with the help of this array. So if I'm on this element that is 1. Then I can check if the five or the next element is greater than this element. Or not. If it is greater than this element, I will buy on the one simple and then on the next day I will sell at 5:00. Right now, since I can buy on the same day again, I can actually again check, OK, I'm going to come here. Suppose I'm on five now. So on five I can check if the next day's price is greater than 5 or less than 5. If it is greater than 5, I can again buy 5, right? So basically I bought here. Then I sold here on the Five. Then I again bought here on the Five. Again bought here on the same day. And then if this is, you know, if this is actually greater, if right now it is 3, but if it was like 7, then I can actually buy again on five. And then on the next day I will simply sell on 7. I'm making another profit. And in the same way, we can also figure out if we should sell or not. So basically if we are at this point, right, if we are on this particular point, that is 6 comma 5, I believe. So in this place the price is 6. And on the next play, the price is going to be 4. So I can see or I can predict with the help of my array that the price is going from six to four. It is on a decline on a decline, right? So I can definitely sell on the six because that is going to be more profitable. If I keep holding through 6 and sell on 4, I'm going to make a loss, right? So it's better to sell on the 6th on this position, simple. But we also have this second example where the prices are. Continuously increasing. So in the second example, first we have one price, then we have two, then we have 3-4 and five. Here the prices are continuously increasing. So if I buy on this police, basically I can buy on this place because I can see that the next day's price is simply higher than the current days price. So I'm going to buy here, then on the next day I can sell. Right. If I want to, I can sell it and I'm going to make a profit of 1, correct. Then I will again check does the 2 or this days price is greater than or less than the next phase price. So I can see that the 2 is less than three, right. So it means I can again buy on this day I can again buy. So this is by I can again buy On this date, right? And I can then on the third day I can sell. So I will again sell here. Then I can again buy on 3rd day because the next gas prices 4 so I will again buy. Right, and then I will sell on 1/5. Sorry, don't 5th, 4th right here so I can sell on 4th. Here I will sell making a profit of one, right? Then I can see that I can again buy on 4th immediately I can buy because the next race price is higher than current days. So I will sell here making a profit of 1. So how much profit did we make? 1 + 1 + 1 + 1, that is 1 + 1 + 1 + 1 is equals to 4, right? We made a profit of four units. So I believe you can understand how the intuition for these kind of problems work, right? But also guys, you can notice that if I just buy on one day and sell on the last day, because the entire thing is continuously increasing, then 5 -, 1 is equals to four, so I don't have to keep on buying. Selling on each point I can just keep going until the prices increasing and at the last day or just before the price is about to decrease I can sell. Right. So this and this are going to end up in the same proper of same result because it is continuously increasing. Of course, if there were some dips like this, then we could not just buy on this place and sell on this place. We will have to account for these points also. But since this is continuously increasing, we can buy on the first answer on the last. But I believe that buying on each place or each point is actually a little bit more intuitive for beginners. And most people, to be honest, buying on each place and selling on each place is a little bit more intuitive for me also. So that's how I coded the code for it. So here is the code for this problem. First of all, we have a few variables that is has stopped. This variable determines whether we have bought a stock or not. If we have bought a stock, we basically have it right. Otherwise we don't have it. Then this is the variable that actually contains the price at which we bought the stock. Remember that we can only buy. A stock one time. Yes, we can buy it one time and then sell it and then again buy it immediately. But we cannot buy a stock on one day and then again buy it on the next day without selling it first. So it's not going to be like, you know, you bought it on this place and then you again bought it on this place without selling it. So if you bought it on the first day and you want to again buy it on the second day, first you have to sell it on the second day and then immediately you can buy it. OK. So at any point we will always have. A single stock with us. So there will always be a single buy price right? On the first day if I bought it, the price was one and on the second day I bought it, the price will be two. OK, so there will be a single price. Now this proper variable will contain the profit that we made throughout the entire time. So here we have a loop that is running on the prices array from zero to second last element. OK, why second last element we are going to see. So here we have a three scenarios. Basically in the first scenario we are seeing that OK, the price of the current today is less than the price of the next day, right. I plus one means next day. So we do have the option to buy today because the next best price is higher than the current is price. So we are going to make a profit for sure if we buy today. But can we buy today that depends on this has stopped variable, right, If we don't have a stock, we can directly buy. We will say has dog is true. Now we have bought it and the buyer price is the current base price. But in case we have a stock, we already bought a stock. What to do? Well, what we can do is we can sell it, we can sell it on the current day and we can add the profit on the profit variable that is current base price minus the price that we bought the stock on, OK. And then we can again buy the stock OK with a new buyer price. For current today's price right? We don't have to, you know, basically reassign this variable to true and false because it is already true. We are just selling it here. OK, booking the prophet, adding the profit to our profit variable and then we are again buying it immediately. So the new buyer price is going to be the current days buyer price, right? Otherwise the last thing or the last scenario is that the price of the current today. For the stock is greater than the price of the next day, it means we are on a decline. So it means if the current disk price, this one is greater than the next day's price, this One South, we are clearly on a decline, OK. So we should sell, correct? So here we can see that I'm setting the has stock to false. And I'm looking at profit, OK, because we previously bought a stock, right? So if we bought a stock previously from the current base price, I'm minusing or basically subtracting the buyer price and I'm basically adding it to the profit plus equals two, OK? So it means I'm adding to the cumulative property and then the new buy price is going to be 0 because we did not buy it anything, right? So the default I'll just keep it as zero because we don't have a stock anymore and in the end. Is, you know, we just continue, right? I mean, if it can happen, OK, it can happen that we have a graph like this, OK, In this graph, there are two points. Or maybe 4 lbs and something like this. OK, so the price kept on increasing and then it it just stayed the same, on the same level and then it kept on increasing. So for these two we don't have to do anything, right? We don't have to sell or buy anything because they are at the same place. So we can just continue. We can just go here without actually doing anything, correct? So that's what this is doing. Just continue. Don't do anything, right? Just continue in the loop. Go to the next element, don't do anything. So now this loop will calculate our complete profit. OK, Now at the end, I also have a line which says that if at the end we still have a stock, OK, we still have a stock. Then you again have to book a profit. OK so when will this be true? So understand that this loop OK the for loop is running from zero to the second last element. OK it is not running till the last element. So this as you can see we have a length of prices array -1 OK So what we are saying is that. Suppose we have this array OK. Like just say hi Yeah, this is the correct example actually. So we have this array. So we are running from zeroth index 01234 till here. OK, so this is what we are running. This is the part of the array that we are running in the for loop. OK till the 2nd last element. OK so as you can see here that this is basically greater than this one. OK, so the five is greater than. 4:00 So at this position or at this place? In our loop, add this place, we are not going to sell, OK, Yes. If after this we had a three here, then we would have sold at four, OK, at this position. But since it is A5, we are not going to sell it means even after our loop we will have a stock in our arsenal. We will still have a stock, right? But we need to sell it. We can actually sell it. We don't need to sell it. We can sell it OK. We can sell it on the 5th day or on the. Next day basically making another profit of five 4. But since we did not reach till the 4th index in our loop because of the array out of bound issues that might actually come. So we only ran till here. OK. So that is why at the end we are checking that if we still have a stock, if we still have a stock, it means that the next or the last elements price was actually higher than the current elements price. So what we did is we just said OK the last element. Minus the means of biasing the last element of the process array. And then we're just subtracting the price of the stock at which we bought it, right? So we just add that to the profit, and then eventually we return the profit. So this is the complete profit. So let's try to run this thing and submit it. And yeah, it works.