Welcome back.
Let's now do a dry run of the approach that we're going to take to solve this question, using the bottom
up approach with just a one dimensional array.
So let's say this is the array which is given to us as the input.
And this is the DP array that we have created.
And we have one place for every index in the array which is given to us.
So the indices over here are zero, one, two, three, four, five and six.
And over here also we have 0123456.
Now this is the relation recurrence relation that we have discussed previously which can be used to
fill this DP table.
We will see more of this in action soon.
Now to start with over here I can fill the value in every cell to be equal to one, because I could
form an increasing subsequence by just including the element at hand.
Remember, every cell over here represents the length of the longest increasing subsequence, where
the element at that particular index is included.
Now, if I were to just take that element alone, I get a length of one.
And that's why we can initialize the values over here as equal to one.
Now again dp at index I is the length of the longest increasing subsequence that has the element at
index I included.
So this is going to be the last element in the increasing subsequence.
And the length of that increasing subsequence is what we will fill in each of these cells.
So to start with, we have filled every cell over here with the value one.
Now let's again write the indices over here.
So it goes from 0 to 6.
Now first we will have another pointer let's say I.
And it's going to take the values from one up to six.
Okay.
And for each value of I when I is.
For example, one J will take all the previous indices as its value.
So initially I is equal to one.
So j will just take the value zero and we will check whether the value at index one which is two, whether
two is greater than the value at index zero which is one.
So we see that two is greater than one.
And therefore it means that this element can be added to the subsequence where we just have this element
over here.
And that's why we have one over here.
Because this is just representing a subsequence where only one element is there.
Now, because two is greater than one, we can add it to this subsequence.
And this value over here becomes two because the subsequence now is one comma two.
Now let's take a look at this over here.
Now nums at I that's equal to two.
And two is greater than nums at j, which is equal to one, and dp at j which is equal to one plus one.
So one plus one is greater than DP at I.
So initially DP at I was one right.
So one plus one is greater than one.
So these two conditions are satisfied.
That's why we will set DP at I to equal DP at j plus one.
And again DP at j is one.
So one plus one gives us two.
And that's how we fill the value two over here.
And again what's the meaning of this.
This is over here two because the subsequence the longest increasing subsequence that can be formed
including this element and considering these elements is one comma two and the length of one comma two
is equal to two.
And we fill that over here.
Now we proceed.
So I comes to the next value, which is equal to and j will take these two values.
Initially j will take the value zero.
So we'll have Jay over here and we will check whether the value over here, which is one, is one greater
than the value at index zero, which is one, we see that one is not greater than one.
And therefore Jay moves ahead.
So j now is equal to one.
And over here we have again one.
And over here we have two.
Now is one greater than two.
No that's also not true.
And therefore notice that nothing has been updated.
And we move the value of I.
Now when we say that nothing has been updated, what does it actually mean?
It means that we can only form an increasing subsequence where there is just one element.
So that's why we have one over here.
And we are not able to add anything that came previously to the subsequence where one is the last added
element.
So that's it.
Now again we move I and I becomes equal to three.
And Jay will take the values from zero up to two.
Initially, Jay will take the value zero.
So I is three and Jay is zero.
So that's these two indices.
So we have the value four over here and the value one over here.
Now we see that four is greater than one.
Therefore yes we can add four to the subsequence which is represented over here and over here.
Again that's this.
This is true.
Now what about this DP at Jay is one and one plus one is greater than DP at I which is one.
So this means that we can update the value for dp at I to equal dp at j plus one, which is one plus
one.
So this value over here gets updated to one plus one which is equal to two.
Now we will see why this is very important.
All right.
So again Jay moves ahead J becomes equal to one.
Now again we compare the values.
So over here we have the value four.
And over here we have the value two.
So four is greater than two.
Therefore, this part over here is satisfied.
And then we check whether DPR j plus one is greater than DPR I.
So over here dpr j is equal to two.
And two plus one is three, and three is greater than this two over here.
Right.
So we need to update the value of DP at I to equal dp at j which is now two plus one.
And that's how this part over here gets changed to equal to three.
Right.
So that's why this is very important.
So what we are doing is for every value of I, we are having another pointer J to iterate through all
the previous values.
And then this over here helps us to understand when it's time to actually update this, because we are
able to form a larger subsequence or a longer subsequence.
Over here we just had one element, but over here we have one comma two.
And updating this actually means that if we add four to this, we just get one comma four.
But if we add four to this subsequence, we get one comma two, comma four.
And this is longer than this, which is why we have to update this to three.
And then we move forward.
So Jay takes the next value which is equal to two.
And we are comparing these two values.
Again we see that four is greater than one.
But this criteria over here is not valid because DPI at J is just one, and one plus one is not greater
than DPI at I, which is already three.
Therefore, we don't update the value over here.
The implication of this is that over here the subsequence is just one, but the subsequence that we
have considered to fill the value three over here is one, two, and four.
And by adding four to just this one over here, we will just get one comma four.
And the length of this is not greater than the length of what we have already considered.
So that's why we don't update the value over here and we move forward.
So I now becomes equal to four.
And then j is again equal to zero.
Now we are considering these two values.
We see that three is greater than one.
And we see that one plus one is greater than two.
And therefore we will update the value over here.
And this will become equal to two.
Again J moves forward.
And over here we are comparing these two values.
We see that three is greater than two.
And we see that two plus one is greater than two.
Therefore we update this two over here to three.
Then we move forward again.
So j is equal to two.
We are comparing this three over here.
And this value over here.
We see that three is greater than one.
But we see that one plus one is not greater than three.
Therefore, we do not update the value for dp at I and j moves forward.
Now we are comparing three and four, and three is not greater than four.
So we don't do anything.
And that's it.
This loop ends and again we move I forward.
Again, J takes the value zero.
And we are comparing these two indices.
So the value over here is for the value over here is one and four is greater than one.
And one plus one is greater than one.
So we can update this to two.
And Jay moves forward.
Now we are comparing four and two and notice that four is greater than two.
And over here we have two and two plus one which is three is greater than two.
Therefore we can update the value for dp at I.
So this becomes three.
And then Jay moves forward.
Now we are comparing this and this four is greater than one again.
But notice that one plus one is not greater than three.
So we don't update the value for dp at I and j moves forward.
Now we are comparing four and four.
Now four is not greater than four.
So we proceed because the question mentions strictly increasing.
So we can't include equal values when building an increasing subsequence.
So we move forward and we are comparing four and three.
And yes four is greater than three.
In this case right four is greater than three, and three plus one is greater than three.
Therefore we will update this three to equal four.
And we are done with this loop.
Now we again move the value of I and j takes the value zero.
And we are comparing five and one, and we see that five is greater than one.
Therefore, over here we change this 1 to 1 plus one which is two.
We move forward.
Now j takes the value two.
Now two plus one is three.
That's greater than what we had over here which was two and five is greater than two as well.
So we update this value to three.
We move forward.
Now five is greater than one.
We're comparing these two values.
Five is greater than one, but one plus one is not greater than three.
So we don't change this value.
And j again moves forward.
Now we are comparing five and four.
Five is greater than four.
And over here we have three.
And over here previously we had three.
Three plus one is four which is greater than three.
Therefore we update this to four.
Now again we move forward.
Now we are comparing five and three.
Five is greater than three.
And over here we have three.
Three plus one is four.
And over here we already have four.
So three plus one which is four is not greater than four.
So we don't update this.
And j moves forward.
Now j is equal to five.
So we are comparing these two indices.
So over here we have five.
And over here we have the value four.
Now five is greater than four.
And over here the value was four right.
For DP at five the value was four.
Now four plus one is equal to five.
And that's greater than four which is what we have over here.
And therefore we update this to five.
And we are done.
So this is our DP table.
Now notice that the values over here are 121334 and five.
So let me write that over here 121334 and five.
Now the answer would be not just the last element.
The answer is whichever is the largest value in this subsequence.
And it so happens that the largest value is at the last place, which is equal to five.
Now this is important.
Why is that so?
Because again notice that if you just had these three elements one, two and one, and if you fill the
DP table it would look like this.
You will have one, you will have two and you will have one.
So the answer is not this element.
The answer in this case would be this two over here.
So basically once we have constructed the DP table we need to identify the largest value which is there
in this table.
And that would give us the answer.