OK, guys, so let's get into the optimal solution for this problem, which is people of our again,
as I said, we will use a trick.
And for that, we are going to need an extraordinary so that extra we'll be using will be called Anina
less.
And let's see the meaning of it so mean less of I mean, from all the leases of life I saw from all
the longest increasing subsequence that have left I.
Take the minimum Lesterville, and let's take a look at the example, let's see, I want to conclude
here mean less of free.
Well, I should take all the leases of land free and that could be free.
Nine, then let's say free nine, 12, free 911, 911, 14, nine, 10, 12 and so on.
So I should choose the one that has the smallest last element and that is obviously free 911.
So midnight of free will actually be 11.
OK, if I take mean less of four.
Let's see what lessons do I have a plan for free 911 14, three, nine, 10, 12, three, nine, 11,
12 and so on.
So the smallest last value of this latest, Blankfort is 12.
So here I am going to have 12 and so on.
This is what the mean less of an array means.
So another definition of this array can be something like this.
The minimum age we have from one to N and DEPI of equals.
Why is that?
Because from all the longest increasing sub sequences of lefi.
But where is the length then.
It fits in the deep.
Remember DPE of I is the lease that is ending in time.
OK, so the last element is going to be EHI and the length of the list is going to be DPE of height.
So if tip of this G is equal to I, then I have a list of Lafi and the last element is going to be.
So I think the minimum of all these options, those are the two definitions of this array.
Now let's take this example and iterate from every element of the initial array and see how to compute
the any less.
And then we will make an observation that will change the whole structure of the problem.
Here I am at my first element, which is free.
And I see Deepthi is one plus that maximum, I have no maximum.
So obviously this debate is going to be one minute less of one is now going to be free.
Because I have a lease of one Soviet element is here now.
I got 11 two, which is nine.
All right, DEPI of mine should be one plus this maximum freeze, less than nine.
So here I have the pictures to submit.
A list of two is going to be.
All right.
Now, for the 11 year I have this one is one.
This one is two.
They're both less than 11.
So here I have three and here I have my 11.
Then I go to 14.
For them, obviously, this is for this is for them that I go to 10 for 14, I have to take all these
elements that are less than himself and my maximum from this is two.
So this is going to be free.
And now I have another release of Love Free.
So I go here and I find another minimum, which is 10.
So this becomes ten instead of 11.
Now I have my 12.
I take a look at all these airlines, I see that almost all of them are less than him, so I take the
maximum from one to three and three.
It's free and this becomes four.
When this becomes four, I go at least less of four and find actually a less element.
So instead of 13, I have 12.
All right.
So you have seen how we iterate through the initial array and build those two arrays.
But the observation I really hope you've actually done is that the last three, the mean last array
will be always increasingly sought in ways that, well, let's suppose that they have two consecutive
elements which are actually the left.
One is greater than the right.
So instead of 10, 12, let's say I have here 12 and here I have that.
Well, this means that I'm going to have a lease of life for that and development.
And so some list like this.
One, two, three.
And the fourth element is that, well, doesn't this means that I have a couple of pieces of land for
free that still end.
And then like, let's say this.
This.
Land free and intact.
Or this one land free and intact.
So if this means less the forest, then this should be maximum, then couldn't be a greater value.
All right.
Because this one is still valid for this position, too.
So first observation we make here is that Disarrayed is increasingly sighted.
And how would this help us solve the problem faster?
Well, what can we actually perform in an increasingly sort of the way that we couldn't in around the
Murray?
And that is binary search.
So here comes the observation number two, and that is when I am computing the DPRK, because that's
the whole problem for computing the value of the P and making that extra for loop.
And I want to get rid of that.
And how will I do this using the Middle East arena.
So let's take a look where I'm actually computing DEPI of AI, OK, DEPI of ah.
Let's say I am looking for all those value.
What is the maximum DEPI of G for all those GS.
But let's think it like this.
This deep of G from that recurrence relation is actually a position in this area, and why is that?
Because as you've seen, when at some element after computing the deep, let's say here was four, I
am going to position deep in the mine lacerate and updating that element like he was 12, completing
the DP was four and a position four.
I've seen that 12 is less than what was here.
So those dips, there are going to be positions here.
And let's take a look at those ages.
I am counting those deposits.
I have to find the maximum deep for any jayce less than eight I.
But who is A.J., A.J. is going to be the last element of that lease of life.
So.
Ages are the values in this area mean less?
I have to find the maximum position in this.
Every position is EDP such that the value at that position in this area, the value is agea is less
than my etai.
So I can perform a binary search on this array and the position where I find the first greater element
than my current element is going to be my DP.
I will start with this example from scratch and I will show you how we are going to build these two
extra arrays in total time.
Complexity of big of and.
Let's take a look.
Initially, I would have I mean, the last array of size zero, no elements in it.
And here I go.
First element is free.
What we will do, we will binary search for the first greater element in this area.
Then even if we do not have such element, then it's going to be the length plus one.
So here the left is zero.
Obviously we don't have any elements.
So left plus one is going to be the answer for this.
So DP of this is going to be left plus one, which is one.
And what do we do now at this position?
DEPI I now update the value in meaningless.
So this is going to be free.
The next step I have here, my nine let's binary search the my fourth position, which is actually greater.
OK, I have no element greater than nine so I'm going to go with land plus one, plus one is two.
So deep of this element is going to be to go with position two and update the value of nine that you'll
ever find in the last.
The first greater element, no such element.
So land plus one again, unlock the cell answer is free.
So this deep is going to be free and a position free.
I update we have value eleven go to fourteen for the greater element nonexisting.
OK, unlock this cell land plus one.
This is going to be my answer and this position update we value fourteen great not position to find
the first greater element.
Now it is 11, so what do I do?
Eleven is a position free, so obviously my answer is going to be free, can be greater than free,
because obviously Latif is going to be for it.
We can't afford the 11th 10 to at least that ends in 11, but to at least that ends in nine.
We can do that.
And if nine is a position to when I add, then the new level of that list is going to be free.
So the solution is free and I go with position free.
And I know that this is the first element greater than that.
So this is greater than that.
So the main last element, a position free, won't be 11 again.
But ehi that they surely know that is going to be better or less than that element.
So here I have a date with that.
OK, so what each element, binary search, the first position of a greater element.
That is going to be our answer.
And that DEPI at that position in the array, we update with that value because you will know it's surely
smaller than the old one last step is going to be 12.
Binary search for greater element is 14.
So my answer here is going to be four and the position four instead of 14, I got 12.
So this is the optimal solution.
Guys, it's Biegel of N Logan.
And why is that?
Because for every element that we iterate, we do a binary search in order to find its DEPI.
And after we know the DP, we just update that element in 01, no further operations needed.
So here I got my optimal solution.