Hey, guys, welcome back to this video.
Now we're going to solve a coding interview problem, best time to buy and sell stock five.
This is a liquid problem.
You're given an integer array price, it's prices.
Why is the price of a given stock on the eight day design an algorithm to find the maximum profit you
may complete at most transactions?
Notice that you may not engage in multiple transactions simultaneously, that means you must sell the
stock before you buy again.
This is the problem statement.
For example, if you are given this array and Cocozza to now we have to find out the maximum profit
we can made from this array by doing ATM card transactions here.
Two transactions if we buy at two and if we sell at four, then we will have profit too.
If we buy at for every sale at one.
Then we will have lots.
OK, so here we can made a profit to buy one transactions.
In the problem statement we see we can meet at most cash transactions.
OK, here we are doing one transactions to find our maximum profit.
So for this given import we have to return to.
If you were given this array and consider, too, we have to find out the maximum profit we can made
from this array, we're allowed to do at most two transactions.
If we buy at two, if we sell at six, then we have profit for then if we buy at a zero and still at
three, we will have profit three.
So we're doing two transactions and we get four plus three calls to seven.
So for this given input, we have to return seven.
If were given this array and Cagle's to six, we have to find out that maximum profit we can made from
this array by doing at card transactions, if we buy at all, if we sell at two, we have profit one,
if we buy at two and still at three, we have profit one.
If we buy at three, if we sell at four, we have profit on.
If we buy at four, if we sell at five, we have profit on.
If we buy at five, if we sell at six, we had profit on, then if we add all the profit, then we get
five.
So for this given input, we can get maximum profit five by doing at most transactions.
Here we are doing five transactions.
Now, how we can approach this problem, this problem is going to be a little bit critical to understand.
Let me explain every single detail that needs to understood this problem.
If we are given this area and close to six, first, we're going to check if the value of K is equal
to the length of the given array or greater, then that means if care is greater than or equal to the
length of the given array, then we can solve this problem exactly the same at the little problem.
One hundred twenty.
Best time to start Bycel too.
OK, now let's see how we can solve this problem when you have Kaisa greater than or equal to the length
of the array.
OK, first will iterate through this area from the second element to the end.
Then we're going to check the current element and the previous element, if we see the current element
is greater than the previous element that will buy at the previous element and will sell at the current
element.
So here.
If we buy it on eBay, let's it we have profit won, then we have currently three, it will buy it to
a pre sale at three we have profit one bean counting for it.
We buy it three.
We sell at four.
We have profit one, then current element five.
If we buy it for sale at five, we have profit one.
Then our current element six it will buy at five and if we sell at six then we have profit on that.
If we add all the profit then we get five.
And this is the concept that he used to solve the problem hundred 122.
I'm not going to go through this with the court for this problem.
I trust the source code to this video.
You can check the link in the description.
This is the catalyst for this problem.
When you have a case greater than or equal to the length of the array, then we have to apply the concept
of this problem.
Best time to start by cell to.
All right.
Now, if you are given this array and Cagle's to to receive care is not greater than or equal to the
length of the area, then how we can solve this problem.
Now, this problem is going to be difficult to understand.
Don't worry.
I'm going to explain you as far as I can.
Now I'm going to go through the intrusion to this problem.
Now let's see how we can solve this problem.
Using dynamic programming when you have care is less than the length of the array.
First, we're going to construct dynamic programming table, and this is our dynamic programming table.
For this input, we're going to use this formula to fill up the dynamic programming table t equals to
max of T i c minus one.
What does this mean?
It means that what I can do best if we do not sell at the current price.
And this means that what I can do best by selling at the current price here we have our error rate three
to six five zero three and here we have our transaction one and two at zero transaction will have all
of you just maximum profit is zero.
So here is zero zero zero zero zero.
All right.
If we sell at the first index, that means if we sell at this index zero, we will have no profit.
So let's we love this first column as well with zero.
Now, our goal is to fill up this dynamic programming table and we'll have our answer right here.
OK, now let's fill up this dynamic preventible using this formula.
Now we're going to fill this box if we do not sell at this current price to put in the best we can do,
best zero.
OK.
Then he sell at the current price what he can do best, two, minus three, so minus one, plus our
profit by selling at index zero at zero transaction and there is a zero sum minus one plus zero is minus
one.
So max of zero and minus one is zero.
So let's insert here zero.
Now let's we love this box, OK, here.
If we do not sell at this current price six holligan the best we can do best is zero.
OK, by just copying value from the left, you bristle at the current price in the best six minus three
three.
So three plus what I can do.
Best Buy selling at price three at zero transaction there is zero so three plus zero.
Then we have another option.
If we buy it to and select six six minus two equals to four.
For plots working the best, you add to a digital transaction, zero support plus zero, so Maxo zero,
three and four is four.
So let's insert here for.
OK, now let's we love this box now what the best if we do not sell at this price five and that is for
Bykov from the left.
Now, if we sell at the price five, protecting the best, so pie minus three to.
Two plus working can best by selling at price three with zero transaction zero two plus zero then.
Five minus two is three, so three plus what I can do best if we sell at that price to at the transaction
and that is zero, the three plus zero.
OK, then five minus six.
That is minus one minus one plus what I can the best Ypersele at six at gillnets transaction there is
zero.
Here we see max of four to three and minus one is four.
So let's insert here for.
Similarly for Ejiro and for three will be evaluated for you can go through using this formula.
OK, now let's we love this box again.
The best if we do not sell at this index to that is zero by copying from the left are the best.
If we sell at this index to and there is two minus three minus one minus one plus.
If we sell at, at one transaction because we're doing our second transaction, we have to get the value
by the first transaction as well because we're allowed here two transactions for this row.
So minus one, plus zero is minus one, so max zero and minus one is zero.
So that's inserted zero then let's we love this box working the best if we do not sell at this price
six and that is zero by copying from the left what I can do best if we sell at price six and that is
six minus three.
So three plus what are going to best buy the first transactions at three there is a zero three plus
zero, then six minus two is four.
So what I can do best is still add two for the first transaction and that is zero.
So Max of three and four is four.
So let's insert here for now, let's calculate the value for this box, what I can do best if we do
not sell at this price.
Five, four.
Right.
My coffee from the left, I get the best if we sell at this price five that is five minus three to plus
by selling at three for the first transaction zero then five minus two three by selling at two for the
first transaction is zero then five minus six minus one plus.
The maximum we can get basically at six for the first transaction, and that is four.
So Max of four to three and three is four.
So let's insert for.
Now, let's calculate value for this box here we have price is zero if we do not sell at this price.
What are you the best for?
Right, by copying from the list, then if we sell at this price, then we have minus three, minus
three plus by selling at three by the first transaction, that is zero, then zero minus two minus two
plus by selling at two for the first transaction, that is zero and zero minus six minus six plus our
profit by selling at price six for first transaction.
And that is false.
Minus six.
Plus four then zero.
Minus five.
So minus five.
Plus the profit that we can make by selling it, by selling at price five that is four.
So max of four, minus three.
Minus two, minus two and minus one is four.
So let's insert here for now we are on the final box here.
We will have our answer here heading into Best Buy.
Do not selling at this price three.
That is four by coughing from the left.
OK then what you can do best if we sell at this price three three minus three is a zero zero plus by
the first transaction that we can made by selling it price three.
That is zero then three minus two one one plus the political made by selling at price to buy first transaction,
then three minus six is minus three, so minus three plus the profit we can made by selling at price
six.
That is four for the first transaction, then three minus five is minus two, minus two, plus the profit
you can make by selling at price five for the first transaction.
So by selling at price five for the first transaction, we can make a profit for the minus two plus
four comma, then T minus zero is three plus.
And what I can do by selling at price zero for the first transaction and that is four.
So Maxo four zero one one two and seven is seven right here the value will be seven.
And this is our answer that we needs to return.
All right.
If we have more transactions like three transactions, then we'll do the same process.
And four is calculations.
We will get the profit from the previous transactions.
OK, if you're on the card transactions, then we will add the value from the second transactions.
OK, and that's how it works for better understanding.
Go through like this.
I'm showing you here by Cagle's two, three and four that you will see how logical it is.
OK, and this is my solution to this problem.
At the end of return, this value seven, the solution will takes bigger off in time complexity where
it is the length of the given area and key is the given integer and it will also take off in space complexity
to construct the dynamic programming table.
Hope you understood this problem and the source code is attached to this video.
Alright guys, thanks for watching this video.
I'll see you in the next video.
Lenticular.