Let's now get into the code and implement the tabulation approach using a 1D array for solving the Liz
question.
So let's say n is the length of the given numb's array.
And we would need a DP array.
Let's just call it dp itself which has the same size okay.
So we can say let DP is equal to array and the length is n itself.
And we will fill, as we have discussed in the previous video, every cell in this array with the value
one okay.
And initially let's say max is equal to one.
So this will be the variable which we will use to keep track of the maximum Liz found so far.
And ultimately we will be just returning Max.
So this is the skeleton of the approach that we will be taking.
Now again over here, if we see that n is equal to zero then we can just return zero okay.
So that's just to handle an edge case.
Now once we have the DP array let's now iterate through the cells in the DP array starting at index
one okay.
So I can say for I is equal to one I less than n because the last valid index is n minus one I plus
plus.
And for each value of I, j will take the values from zero up to I minus one.
So I can say for j is equal to zero j less than I j plus plus.
All right.
Now what we will do is we will take pairs of I and J.
And we will try to see whether numb's at I is greater than numb's at J.
And if we see that that is the case, then we will check whether depee at J plus one okay is greater
than depee at I.
Because if that is the case, then we would have identified a longer subsequence ending with the value
at index I.
And therefore over here we would say depee at I, which initially had the value one, because that's
what we filled over here in the DP table at every cell.
So we would change that value to depee at j plus one.
Okay.
So again in this case the subsequence that we are building would be ending with the value at index I.
And after that, once we are out of this for loop, remember we have to check whether the value that
we got for DP at I is greater than max, because ultimately we are returning max over here.
So let's check that.
So if dp at I is greater than max, then we would just say max is equal to dp at I.
All right.
So this helps us because otherwise we would have to pass through the DP array one more time to identify
the largest value in the DP array.
And that's it.
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.