Welcome to this video now we're going to cover a recording interview question with the time to buy and
sell stock.
Here's the problem statement.
Say you have an array for which the right element is the price of a given stock.
One day I if you were only permitted to complete at most one transaction, buy one and sell one share
of the stock.
Now we have to design the algorithms to find the maximum profit.
Know that you cannot sell a stock before you buy one.
Let's suppose that you were given this array.
The value represent price.
OK, if we buy at this price one and if we sell at this price six, then we will have our profit six
minus one five.
So if we buy at this price all and the principal at this price six, then we will have maximum profit
five.
If you were given this array as input.
Then we will have the maximum profit zero.
Because if we buy at the end of the day, we will have lost.
There is no chance to make a profit in this area.
So the maximum profit is zero that we can get if we do not buy a product.
So for this area, we have to return zero.
Now let's see how we can solve this problem.
Let's assume that this is our given area.
First, we're going to charge the first element as minimum by price.
OK, let's about this is our bipartite that is seven.
If we buy at seven, then we have minimum seven, then we're going to use loof iterate from this element
to this element four and we're going to initialized a variable max prophetical to zero.
If we sell at this price one, then we will have plus one, minus seven to minus six.
So we will have lots of six dollars.
Then we're going to take does the current element is less than minimum.
Yes, it is.
We see this current element on is less than minimum.
So we're going to change minimum to this current element.
One, OK, then our current element is five.
Now, if we buy at this price on and if we sell at this price five, then we'll have maximum profit,
five minus one that is for the maximum zero and four is for max profit, equal to four.
Then we're going to take does the current element is less than minimum?
No.
So let's move to the next element in this case three.
Now, if we sell at this price, then we will have our maximum profit, three minus one that is to the
max of four and two is for.
So in this case, it makes perfect sense for also we'll take those three is less than minimum.
No.
So will not change the value of minimum variable, then let's move to the next element in this case
six, if we sell at this price six, then we'll have max profit, six minus one equals to five.
So max of five and four is five max, probably to five.
Also will check does six is less than minimum.
No.
So all the change minimum variable.
Now let's move to the next element in this case, for if we sell at this price, then we will have maximum
profit for minus one equals to three.
So max of five and three is five.
So we see that our maximum profit we can have for this given error is five.
So we can have our maximum profit five if we buy at this price on and if we sell at this price, six,
if we convert this array into Graboff, then we will see this graphic representations price even at
index zero here we have zero at Cejudo, we have price seven at index one, we have price one.
At index two, we have price five.
At index three, we have price three.
At Index four, we have price six.
And at index five we have price for.
You can see that if we buy at this minimum price, if we sell at this maximum price, then we will have
maximum profit and that we can get by substract in this fellow.
One from six to six minus on his five will have our maximum profit for the given area is five.
Now let's see how my solution might look like into the code.
First, I'm going to declare a function max profit that takes pride away as input.
Let's suppose that this is our human error.
Then we're going to check if the length of the flight array is equal to zero, then it will return zero.
Then we're going to declare a variable max profit goals to zero, then buy at prices zero.
And this all points to the first element in this case seven.
Then we're going to run and live from this element to this element for current element one, we're going
to calculate the max profit.
If we sell at this price, one, then will have max profit zero because one minus seven is minus six.
So max of minus six and zero zero.
So max profit is zero.
Then we're going to take as the current price is less, then by Friday, then we'll change the buy price
to current price in this market.
We're going to change the buy price to current price since it match this condition.
OK, then the next iteration of this love, it will point to this element, five five minus one is four
smacks of one and four is four.
OK, and this condition false for this current element, then three three minus one is two max of four
and two is four.
Also, this condition is false for this current telemetry, then we have our current equipment, six
six minus one is five, Maxell four and five is five.
So let's change this to five for this element six, this condition also false.
Then we have next element for four.
Minus one is three smacks of five and three is five.
We are done with this live at the end.
We're going to return max profit we have.
Max, we're really close to five, so this function, Max, profit will return 5:00, and this is my
solution to this problem.
This solution will take off in time, complexity or in the Lindela given away.
And it takes constant space complexity since we just using two variable max profit and Biette already
guise of this concept was clear.
If you have any question, if you have any suggestion, let us know.
Thanks for watching this video.
I will see you in the next video.
Till then, take care.