OK, guys, here we go.
Initially, I'm going to have those two extra arrays deep and mean, less defined globally, and there
is just one function and I call the function fateless is going to return an integer, obviously the
length of the list and is going to take two parameters, my array and its left.
Then I'm going to do the step for the first element by hand so I can initialize the deep and mean list
arrays.
So I have the of one is going to be one obviously, but is one meaning less than one is now a one.
And the length of the mean Lestari land is also globally defined is going to be.
Now what I unlocked basically the first set and the four I'm from true to position and a plus plus and
now I check for one thing, if 18 is greater than Elastoplast, that means, as we've seen in the example,
that my element has no greater element in the ministry.
So what do I do?
The answer is going to be land plus one, as we've seen, and I unlock the next step.
So land plus plus unlock the next cell.
In the mystery, DEPI of AI is now lean and mean.
Less of land is now a L.
That means I'm going to have at least one element which is greater or equal than mine.
So here I'm going to apply the function upward bound, which takes three parameters.
And those are two pointers, which are the beginning and the end of the array, because as we know,
unary is and continuously block of memory.
So it has a beginning, which is mean less plus one, the first element of the array and an ending which
is midlist plus land, plus what the ending is actually mean, less plus land.
But this function takes the first pointer inclusively and the last one exclusively.
So that's why the plus one and then the value that we want to buy research and obviously we will find
the research, the value.
And there are basically two functions which are lower bound and upper bound, lower bone function with
the same syntax searches for the first greater or equal element, in-memory upper bound searches for
the first greater element in this area from this beginning to this and greater than this value.
So it's basically one thing and then it returns another pointer.
But I don't want the pointer.
I want the position of that value.
So I just subtract, mean less midlist, which is the name of the array.
As we know, he's another pointer.
So if I have the pointer mean less plus then that actually means position.
So only I subtract this value, which is the value of the pointer.
Right now I have the desired position.
What do I do?
I should be careful at one specific case here.
We know because we are here at the House that the last element of the last array is greater or equal
to my value.
OK, but the problem is like this.
When I try to go for the force, the value that is greater than my value.
OK, I can have something like that, meaning the there can be one, two, three, and my value, I
could actually be free.
OK, again, this value can be less than a greater or equal.
So the problem is whether it is equal.
And why is that?
Because my upper bound function, if it doesn't find any value strictly greater than this one that we
are searching, is going to return me this pointer.
So position for and it's not actually right to say that the peak of this is going to be for it because
we need longest strickly increasing subsequence.
That's the point.
So if you mean less of B minus one, if the element before what I found is equal to eight, because
we saw that this is possibly minus minus.
So here I'm going to have my pointer and position free, which is definitely great because that answer
is free.
Like in this example, so deep of A equals B minus of B equals er and that's all this.
After we successfully finish this Y loop, we have to return the answer so I can iterate through the
debris and find the maximum value as we've seen.
Or I can do another thing.
I can return the length of the last array because from the definition of adultery, the length of it
is obviously going to be equal to the length of the longest increasing subsequence ever.
So we've seen how to solve the problem in L squared.
Then we proceeded with this extraordinary sorted in and again, rather good.
And that's all I really hope you've understood.
And I can do this in the next lesson by.