- Hello friends.
My name is Tushar,
and today we are gonna discuss the question,
longest increasing subsequence length.
What does this mean?
It means that given a sequence,
find the longest subsequence
such that all the elements in the subsequence
are in a sorted order.
So for this example, our longest increasing subsequence
is -1, 0, 2, and 3.
So the length is four.
For this example, the longest increasing subsequence
will be 2, 5, and 8.
So the length will be three.
So, how do we solve it?
Yes, we will have to use dynamic programming
to solve this problem.
Let's try to solve this particular example.
We start with a temporary array of the same size
as the original array.
Now, what do we know about the longest increasing subsequence
for every element?
You can clearly see that at least the longest increasing subsequence
is of length one at every position.
So let's fill this one with one initially.
Okay.
Now let's have i start from the first position.
i be at this position, and j is at index zero.
If element at j is less than element at i,
that means that the longest increasing subsequence
at i will at least be the longest increasing subsequence at j, plus one.
So this becomes two.
Okay.
Now, as soon as j reaches i, we reset,
and we make i plus one.
And j again starts from zero.
If element at j is less than i,
which is not in this case, we do nothing.
We increase j by one.
Again, element at j is not less than i,
so we do nothing, and reset i to three,
and j again to zero.
element at j is again not less than i, so we do nothing.
Here also, element at j will not be less than i,
so we come here.
Element at j is less than element at i,
so what that means is the longest increasing subsequence
at i will at least be the longest increasing subsequence
at j plus one.
So let's make this guy two.
And then we have i here
and j again starts from zero.
Now, element at j is less than element at i,
so the longest increasing subsequence will be,
at six, will at least be one plus one, so two. so the longest increasing subsequence will be,
at six, will at least be one plus one, so two.
Now j becomes one.
Element at j is less than element at i,
so the longest increasing subsequence at i
will at least be two plus one, so three.
Okay.
Now, j becomes two.
So the element at j is less than element at i, yes,
but the longest increasing subsequence at six
is already of size three,
while if we include this one,
the longest increasing subsequence at six,
we can do as one plus one: two.
So why do use that value when I'm already getting three
from three and four?
So I will not doing anything about it.
So now j becomes three.
Again, the longest increasing sub--
Since element at j is less than i,
the longest increasing subsequence at six
will be two plus one: three.
But we already have three from three and four,
so it makes no difference.
So now i points at two,
and j again starts from zero.
Element at j is not less than element at i,
element at j is not less than element at i,
so j becomes two.
Element at j is less than i,
so this value becomes two.
Okay.
Again, element at j is less than element at i,
so this value becomes two plus one: three.
Okay.
Element at j is not less than element at i,
so we do nothing about it.
So now, our i is this.
Element at j is not less than element at i,
element at j is not less than element at i,
so j becomes two.
Element at j is less than element at i,
so here it makes it two, okay?
This guy is, again, less than this guy,
so this becomes three,
and j points to six.
This guy is not less than this guy,
so finally j points to two.
This guy is less than this guy,
so the longest increasing subsequence here
will be three plus one: four.
Once this array is built, all you have to do
is iterate through this array
and get the maximum value, which is the length
of your longest increasing subsequence.
So what is our formula here?
Our formula is pretty straightforward.
If...
arr[j] is less than arr[i]
then T[i] is going to max
of what is already in i or T[j] plus one.
You can find the full solution at link,
github.com/mission-peace/interview/wiki.
Thank you.