Welcome back.
Let's now get into the code for implementing the tabulation approach for solving the Liz question.
And over here we are discussing the tabulation approach using a 2D DP array.
And we will discuss the approach using a 1D array in a later video.
Now again, I have quickly drawn this out over here so that we can visualize what we're going to implement
over here.
So we have this 2D array.
And let's say this is the Nums array which is given to us.
Notice that the values for pref go from minus one up to one okay.
So again minus one means nothing.
And then zero and one.
That's this zero and this one.
Now to implement this or represent this in this DP array we will be adding one to it.
So minus one will be changed to zero.
Zero will be changed to one and one will be changed to two okay.
And over here we have curr.
And the values for curve span from zero up to two.
And as we have discussed in the previous video these are the initial conditions that we need okay.
So we will have zero field over here and here.
And then we would just need to iterate over these cells right.
We would first start over here.
Then we come over here.
Then we come over here and then here and then here and then here.
And finally this is where we would be getting our answer.
Because notice this problem over here represents the scenario where you can include elements starting
and index zero and to the right of it.
So in fact you can include all of the elements.
And prev over here is equal to minus one.
Which means that nothing has been added to the subsequence that we are building.
And that is the original problem which has been given to us.
All right.
Now let's get into the code.
So let's say n is the length of the nums array which is given to us.
And let's create a 2D dp array which will have n plus one rows and n plus one columns.
Okay.
All right then over here we'll have array and plus one because we want n plus one columns.
And what we will do is we will fill every cell in the DP array with the value zero.
And this will take care of the initialization requirement.
Right.
Because we are filling every cell with the value zero automatically, these cells also will be filled
with the value zero.
And then we do not need to explicitly write code for that.
All right.
So let's get back.
Now let's iterate through the remaining cells again quickly pulling up our drawing.
Notice that we just need to iterate through these cells over here.
So at this point I for example is equal to n minus one.
And we will go till I is equal to zero okay.
So from two up to zero two is n minus one.
And this is zero.
And for example when I is equal to n minus one notice that j takes the values from I up to zero.
So that is what you can see over here right.
So let's use that to build the nested for loops that we will need to iterate through these cells specifically
okay.
So I can say for let I is equal to n minus one I greater than or equal to zero I minus minus.
And for let j is equal to I, j greater than or equal to zero j minus minus okay.
All right.
So these are the cells that we are going to visit over here.
And for each of these combinations we will have to calculate exclude.
And we'll have to calculate include okay.
Now again let's just write let include over here is equal to zero.
And the reason for that is we will not always be able to include the particular item or value that we
are considering.
And finally over here we would be saying depee at I j is the maximum between exclude and include.
Now first what would be exclude.
Now exclude is that we have to exclude or not take the current element that we are considering and then
the previous value also does not change.
Right.
So that would be depee at I plus one and j itself.
Okay.
So we have J itself over here because the previous value does not change.
And we have I plus one over here because we are moving the index by one.
And again remember this means that you can start taking elements from index I plus one till the end
of the Nums array.
So that is what this means right.
So we have not included the element at index I.
And we can start including elements starting at index I plus one.
So this is the exclude value.
Now over here we have initialized include to be equal to zero.
Now let's go ahead and check whether we can in fact include the element that we are considering.
And for that either prev has to be equal to minus one.
And again remember we have seen that we are incrementing the prev value by one to be able to fit it
into the dp array.
So whatever we get over here, as j has to be subtracted by one to get the actual prev value.
And we are going to check whether j minus one is equal to minus one, which would mean that nothing
has been added to the subsequence as of now, and therefore we will be able to include the element that
we are considering into the subsequence.
Now, if this is not the case, then we will have to check whether numb's at I is greater than numb's
at prev okay.
And again prev over here would be equal to j minus one.
So we are checking whether numb's at I is greater than numb's at j minus one.
Quickly repeating why do we have j minus one over here?
That's because to get prev from the value of j, we have to subtract one from it because we added one
to prev to get to j.
Okay.
So that's why we have j minus one over here.
And if either of these is true then we can say that include is equal to one plus depee at I plus one.
And then the new prev value which is the value at I or index I.
But again because whenever we have a value for prev and when we want to include it into the DP table,
we have to increment it by one.
Okay, so that's DP at I plus one, I plus one.
And over here we are doing one plus because we just included a particular element to the subsequence
we are building.
Okay.
And then over here we have dp at I j is equal to the maximum between exclude and include.
And that should do it.
Now once we are out of this for loop we have to return DP at zero zero.
Because we have discussed this is where we will be getting our answer again.
I've quickly noticed there is an error over here, so I've missed this.
All right, now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the tabulation approach using a 2D array for solving the Liz question.