Hey there and welcome back!
In the previous videos we have discussed the bottom up or tabulation approach for the list question
using a two dimensional array.
Now let's get started solving this question by just using a one dimensional array.
Now, previously I had mentioned that this can be done because the state of a subproblem can be represented
with just one variable.
So what does this mean?
Let's get started with this.
So we know that in DP problems we need to solve subproblems.
And we need to store those solutions and then use those solutions to come up with the solution to the
original problem.
So we need to store the answer to a subproblem or a particular state of the given problem.
Now for this question.
For the Liz question, the state of the question is one dimensional.
In nature, because we can represent a subproblem with just one variable.
Now what do I mean with this?
Let's take an example.
Let's say the array which is given to us is this array over here.
Now if I have a DP table over here which is one dimensional in nature, and if I have one over one value
over here for every index in the array which is given to me.
So note is over here.
Also I go from 0 to 6.
So if I have an array like this, then I can represent the answers to the subproblems in a way that
dp at index I would represent the longest increasing subsequence, including the element at the ith
index.
So for example, if we talk about dp at three, then it would represent the length of the longest increasing
subsequence for these elements over here in a way that we are also including this element.
So if I have a DP table in this manner, and if I am able to iterate over all the elements of the array
given to me and fill out this DP table, then I would just need to identify which is the greatest value
in the DP table over here, to get the length of the longest increasing subsequence.
Now we will see more of this when we do a dry run of the algorithm.
But over here let's first think how can we identify DP at one if we know the value for dp at zero?
Or in other words, what is the recurrence relation that we can use to iterate over the elements of
the array given to us and fill out this DP table?
So first let's spend some time building this intuition.
And then we will come back and do a dry run of the algorithm and fill this table to understand how this
works.
So over here let's say this is the array which is given to us.
And we have a DP table over here.
So we are trying to build the intuition that we will use to solve this question.
Now I told you that we need to fill the values in this DP table over here such that dp at index I represents
the length.
Of the longest increasing subsequence, where the element at index I.
Is included.
When we take a look at the dry run, we will understand this in depth.
But over here let's just develop the intuition.
So if this is what I want, and if this is the array which is given to me, once I am done filling up
values into this DP table over here, it will look like this 1213345.
Now again, why is this?
So let's try to understand it.
So initially I'm only considering this element.
And that's just one element.
So I have one over here.
Then for this element this is zero.
Sorry this is zero.
This is one this is 2345 and 601234, five and six.
So when I'm trying to fill depee at index one, I can use these values over here.
And I have to include this element.
Now notice that by including this element I can in fact form an increasing subsequence of length two.
And that's why I have two over here.
Now for example, let's take another case.
If I were to consider this element over here, notice that I can form a strictly increasing subsequence
by including this element and including these two elements as well.
So that's why I have the value three over here.
But when it comes to this element over here which is at index two right.
So that's this over here.
So DP at two I need to form a strictly increasing subsequence in which this element is included.
And the only increasing subsequence that I can form by including this element and considering these
possible values is just having this element alone.
So that's why the length of that increasing subsequence is equal to one.
So we have understood what this DP over here is.
Just to summarize over here dp at index I is the length.
Of the longest increasing subsequence, where the element at the ith index is included.
So this is how we will fill the DP table over here.
Now let's quickly discuss one more interesting thing over here.
Notice that for this index that's 0123.
That's this over here.
And this is four.
So this is four over here for DP at index three.
The longest increasing subsequence is 124.
And for DPI at index four, which is this over here I have to include this value.
So I have three over here.
The longest increasing subsequence is one, two, three.
Again I have to include this value and I can consider these elements.
So that's why the longest increasing subsequence is 123 and its length is equal to three.
Now let's also think how would the algorithm identify the length of the longest increasing subsequence
up to the element that we are considering, and including that particular element?
For example, let's say we are trying to find this value over here, and let's say we have already filled
these values in the DP table.
Now, when we are trying to fill this value, what we will do is let's say a pointer is pointing to
this index and we will have another pointer that will go through all the values which are prior to this
in the DP table over here.
So that's these values over here.
And we will see whether the value over here which is four is greater than the value at each respective
place.
So initially we will see that four is greater than one.
Therefore, yes, this is a valid, uh, thing to add to the subsequence, where four is the last element
that is added to it.
And over here we know that the length of the longest increasing subsequence, which includes this element
is one.
Now we come to the next element over here.
See that it's two, and yes, two is less than 4 or 4 is greater than two.
So this also four also could be added to a subsequence where two was the last added element.
And over here we have one four is greater than one.
So all of these are valid.
Now that we have identified the places where we could add four two, we need to identify where to add
it so that we are actually getting the longest increasing subsequence.
So this over here this one over here represents this subsequence.
This two over here represents the subsequence one comma two.
And this one over here represents the subsequence one.
And we have seen that four is greater than the last element in each of these instances.
Now if I were to add four over here, I'll get one comma four.
If I were to add four in this subsequence, I'll get one, two and four.
And if I were to add four to this subsequence, I again get one comma four.
Notice that I get the longest increasing subsequence in this case where depee had the largest value.
So that's why among these I will choose this one and add one to it, and in this way I will get the
value three, which I can fill at this position.
So this is how I can find the value over here.
Now let's see the same thing about this index over here.
So how do I find this value.
Again the subproblem is that we have all these values in the DP table.
And we are trying to find this value over here.
So what we would do is we go and take a look at the value at this index in the array, which is given
to us, which is equal to three.
Again we have the indices right.
So we'll use the indices to find this.
So this is index four.
This is also index four.
So we get the value three.
Now we need another pointer to iterate over all these values and identify all the values which are less
than three.
Or all the cases where the value over here is less than 3 or 3 is greater than the value.
So let's do that.
And we notice that we have values less than three over here, over here and over here.
But over here we have the value four.
So we could not add three to the subsequence that was formed over here.
The longest increasing subsequence including four.
So this is out but these three are in.
So again this subsequence is one.
This is one comma two and this is one.
Now we just need to know where to add three.
And because the largest among these is this we will add one to that value.
And we get three over here.
So this is how we will go ahead and fill the DP table.
But again, over here we are just trying to build an intuition and we are just trying to understand
why this works.
Now we will see this in greater detail in the next video where we will dry run the algorithm filling
the DP table.
Now that we have understood the intuition over here, let's come back to the question that we were discussing,
and let's try to write the recurrence relation that can be used to fill the DP table over here.
So if we know the value for DP at zero, how do we find the next value in the DP table.
So for this we will have two pointers.
Let's say I is pointing to this index over here.
We will need another pointer to go over all the previous values in the array which is given to us,
and we will check whether numb's at I is greater than numb's at j in each index.
And if we see that yes, that's the case, then we will check whether dp at j plus one is greater than
DP at I.
And if that is the case, we would fill that value as dp at I.
And again this would become very clear when we walk through the algorithm and do a dry run.
But over here let's just try to pin it down.
So we will check whether the value over here is greater than the value at index j, and we will check
whether dp at j plus one is greater than dp at I.
Now this part over here is required because earlier remember we had seen that I could add this four
to this sequence over here.
Again over here we had one over here.
We had two over here we had one.
And then over here we had to fill the value.
Remember this over here.
This one represented this sequence.
This two represented one comma two and this one represented one.
So we could add four to either of these sequences.
So that's why we need this part over here to identify which is the correct place to add four.
Or initially you would just go ahead and add four to this subsequence.
So we get one comma four.
But then when we get a better opportunity over here one comma two comma four, we have to change the
value over here to three.
Now again this will become more clear in the next video when we do the dry run.
But if these two conditions are satisfied then we would set DP at I is equal to dp at j plus one, because
we are adding the element at index I to that particular subsequence.
For example, over here the subsequence is one comma two, because of which the length is two.
And when we add dp at I to it, we get one, two and four, and the length over here is two plus one,
which is equal to three.
And that's what this step is for.
All right.
So we have discussed the approach on a high level that we can take to implement the bottom up list solution
with just a 1D array.
And we have also developed an intuition about why this works.
In the next video let's discuss this in detail.
And let's do a dry run to thoroughly understand this.