Welcome to this video.
In this video, you're going to sow discord are going to be caution.
Best time to buy and sell stock, too.
In this problem we're given an array of integers.
Is integers represent the price of a stock at a certain date.
This integer seven indicates the price of a stock.
At first it is one.
This integer seven represents.
This integer seven means the price of a stock.
At this D one is seven.
This is dear one.
This is the index.
Okay.
But this is the one that due to the price is one at three the price.
The price is five and so on.
Now we have to return the maximum profit we can meet.
We can engage in multiple transactions.
We can make transactions as many times as we want.
We cannot made multiple transactions simultaneously.
We have to sell the stock before buy one.
Okay.
So if we buy at these pride and if we sell at this price, it will have the profit for.
And if we buy at this price and the sale at this price, we'll have the profit three.
So the maximum profit we can made is seven.
So for this, given ali of integers, we have to read in seven.
For example, if we we're given these area of integers we know is integers represents the pride of a
stock.
The up look at this one is one.
The price of stock at the two is two.
And so what now?
If we if we buy at price one and if we sell at price to have the profit to one, if we buy at two and
if we sell at three, we will have we will have profit one.
If we buy at three, if we sell at four, we will have profit one.
If we buy it for every sale at five, we will have profit of one.
And if we buy it five, and if we sell at six, we will have profit one.
We cannot engage in multiple transaction simultaneously.
We have to sell the stock before buy one.
Okay, so we are selling it two under buying at two, it's allowed.
So for this given area of integers, we have to return five.
This is the problem.
Now, how to solve this problem?
This problem actually pretty straightforward.
To understand this problem, let's draw a graph.
You can look at a graph.
Then this problem becomes so easy to understand.
Now let's draw a graph.
This is the graph for this area.
And this is the graph for this area.
This graph for this area.
And this graph for these areas.
Now, if we compare is here we have 7.1.
We see seven on high price and one at low price.
So we cannot buy at seven and we cannot sell that one.
Now let's compare this pair since you are allowed multiple transaction.
So here we see this is low, right?
And this is a high price.
So if we buy here and if we sell here, we can gain oh, we can make some profit.
So we'll have the profit here.
Five minus one is four.
Now we see this is decreasing in this pair.
We cannot buy here.
We cannot sell here.
If we do that, we'll have a lot.
Now, if we buy here, if we sell here, you'll have some profit.
That is six minus three, which is three.
And if you compare this pair, we see that we'll have some lot if we buy here and if we sell here.
So we have to do profit here savvy by looking at this graph, we see that if we compare is here, if
we buy at a lower price and if we sell at high price for is here, then it can make the maximum profit
for this area.
If we buy here, we sell her, we will have profit one.
If we buy here, if we sell here, you'll have profit one and so on.
Okay, so we can made here to grow FY profit.
This is how we can solve this problem first and compared this we see decreasing, not increasing.
So will not buy at lift and not sell here.
Then for this pier we will buy here and will sell here because this is increasing.
Now here we see for this to appear two will unit buy at five will not select three.
Then for this pier it's increasing so we can buy it.
You can select six been here.
We see that we cannot buy at six and we cannot sell it for.
So this is our increasing portion increasing pier.
So for this to appear to be made to.
Transaction will have maximum profits.
Seven four is coming from here and three is coming from here.
So four plus three equals two seven.
So for this given input, we should return seven.
And for this period we see every single power in increasing order, every single peer so we can meet
here to do five profits by buying and selling at is pair.
This is how we can solve this problem.
In that case, we have to scan the tariff once.
So the time complexity is of in and this space complexity is of one.
No, let's write out the code now let's implement our algorithm first.
Let's create a variable profit equals to zero.
Our initial profit is zero.
Now I'm going to iterate from second element I class to one I liston prices start length I plus but
will have here pair the first limit in the period at index I minus one and add index I so let's compare
if if price which I minus one is less than price which I then let's calculate profit so profit plus
equal to price it I minus prices I minus one at the end will return the profit, the minimum length.
Our prices are going to be one.
If the later prices is one, this loop will not be executed.
It will just return zero.
This algorithm will takes off in time, complexity and of one space complexity.
Now let's run this code.
Accepted.
Let's submit it accepted.
We have solved this problem.
Thanks for watching this video.