Hey there and welcome back.
Let's now proceed and draw the recursion tree for the approach that we have discussed for solving the
Liz question.
Now for this, we will be writing a function that we will be recursively calling.
Now let's say that function is called Liz.
Now to this function.
At every point we would have to pass the index that is being currently considered for including in the
subsequence at hand.
So let's call that curr.
And we also would have to pass the index of the element that was previously included in the subsequence
at hand.
So that's curr and prev.
Now this is required because to decide whether we can include the element at index curr in the subsequence
at hand, we would need to know whether the value of the element at this index is greater than the value
at this index over here, because the question asks us to develop a strictly increasing subsequence.
So Liz Curr prev will return the longest increasing subsequence starting at index ker to the right with
values greater than the value at index prev.
So for example, if again this is the array which is given to us, which is one, two, three, the
indices are zero, one and two.
Let's say at one point curr was equal to one and let's say prev is equal to zero.
This means that the previously included value in the subsequence is the value at index zero, which
is one, and the value that we are considering for inclusion is the value at index one, which is this
value over here.
And what this call will return is the length of the longest increasing subsequence starting at index
curr.
So it will take into consideration elements starting at this index to the right.
So that's two and three.
So this call over here will return the longest increasing subsequence of this array over here with values.
Greater than one because one is the value at the previous index, which is index zero.
So you have one over here.
So this is what l I s curve prev will return.
And also remember that when we start off with the function calls initially we would have nothing added
to a subsequence that we are considering.
And at that point we will set prev to equal minus one.
So if prev is not equal to minus one, it means that the subsequence which we are considering already
has some elements included, and in that case, values greater than the value at index prev only can
be included to the subsequence.
All right.
So keeping this in mind let's proceed and draw the recursion tree for this question.
So initially we have our array.
That's 123.
The indices are zero one and two.
So we make a call to the list function.
And we pass index cur at this point, which is zero because we have decided to go from zero to the last
index.
So cur would be equal to zero.
And because nothing has been included in the subsequence so far, we set prev to equal minus one.
Now we have two choices with respect to this element at index zero, which is either to exclude this
element or include this element.
If we choose to exclude this element, we have to increment cur.
So cur becomes one, but prev stays the same because nothing again has been included as of now.
Over here nothing was included and we just excluded this element.
So still nothing is included.
So prev does not change and prev is still minus one.
Again over here.
When we are considering the element at index one, we have two choices which is to exclude this element
or include this element.
Now over here, when we exclude this element, we proceed to index two and prev does not change.
Prev is still minus one.
Again we have two choices to exclude the element at index two or include the element over here and when
we exclude it curve becomes three and prev stays minus one.
And this call over here will return the value zero.
Because note is that cur is now greater than the last index which was two.
So we have hit the base case and therefore we will just return zero over here.
Then we'll go down this branch over here, which is to include the element at index two.
And when we do that cur again will become three, but prev will become two because the element at index
two was included.
So this value becomes prev.
Now in this call again we will return zero because we have hit the base case over here because this
is three which is greater than two which is the last valid index.
But because we have included one element we have to add one to this.
So this over here will return zero.
And finally include will become one plus zero which is equal to one.
So we get exclude over here as zero and include as one.
And the greater value between exclude and include between 0 and 1 is one.
And therefore this call over here will return the value one.
All right, so we're done with this branch over here.
Now we go down this branch.
So we were at one comma minus one.
And because we are including this, whatever we have over here, we have to again increment the value
of cur.
So cur becomes two.
And prev also changes from minus one to this value, which is the latest value which was included.
Now again remember before we include we have to check whether either nothing has been included and which
is the case over here.
We have prev to equal minus one.
So nothing has been included as of now.
And therefore we can go ahead and include this value.
If this was not the case then we would have to check that the value at the index curve is greater than
the value at index prev.
So over here, because prev is minus one we can go ahead and include this.
So we have two comma one over here.
And because we have included one element we have to do a plus one over here.
Two whatever gets returned over here.
So we have two comma one.
And again we have two choices with respect to the element at index two, which is to either exclude
it or include it.
When we exclude it we get three comma one.
So prev does not change.
And because this is three which is greater than two, this returns zero.
Now when it comes to including this, we are considering the element at index two which has a value
of three.
And the previously included element was the element at index one, which has a value of two.
Now, because three is greater than two, we can include this.
So in this branch when we include it, include becomes one plus this call over here which is three comma
two.
Notice that prev has changed from 1 to 2 because two is the most recently added element to the subsequence.
Now three comma two again will return zero because three is greater than the last valid index, which
is two.
So this also will return zero and the include branch will become one plus zero, which is equal to one.
So over here exclude is equal to zero and include becomes one.
So two comma one will return the value one which is the greater among these two.
So notice over here because over here we were including to this one we have to add one.
So the include branch over here becomes equal to two.
And exclude is equal to one.
And between 1 and 2 the greater value is two.
So this over here will return the value two.
And we're done with this branch.
Now let's go down this branch.
So cur is equal to zero and prev is equal to minus one.
And because prev is equal to minus one, nothing has been as of now included in the subsequence at hand.
And we can go ahead and include the value at index zero.
So when we include we have to do plus one.
So include is equal to one plus this recursive call over here where cur has been incremented and prev
has been changed to this value over here because we have included it.
So the latest included element is at index zero.
Now to solve the call where we are passing one comma zero to the loss function, we have again two possibilities.
That is either to exclude the element at index one or include the element at index one.
Now, when we exclude the element, we just have to increment cur and prev stays as it is, so the call
becomes two comma zero, where car is two and prev is still zero.
And then to solve two comma zero we again have two possibilities.
We have exclude and include and in the exclude branch again we increment cur.
So we get three over here and prev stays the same which is zero.
Now three comma zero will return zero because this three is greater than this two over here which is
the last valid index.
So we have hit the base case and we return zero over here.
Now in the include branch, we are considering to include the element at index two, and the previously
included element is the element at index zero, which has a value of one.
So the element at index two, which is three, is greater than one, and therefore we can include this.
So when we include it we have to add one.
So include is equal to one plus the recursive call where cur is equal to three and prev is changed to
this value over here which is two.
So three comma two will again return zero because three is greater than this two over here.
Right.
So we have hit the base case.
So this over here will return zero and include becomes one plus zero which is equal to one.
So exclude is zero and include is one.
So the greater among these two is one.
And therefore this call over here will return the value one.
And then we come down over here.
Now what's this problem over here we have the element at index zero as the previous included element
which has a value one.
And we are considering to include the element at index one which has a value two.
Now two is greater than one.
Therefore we can include.
So when we include we have to do plus one.
So include is equal to one plus the recursive call where cur is equal to two and prev is equal to this
one.
Over here.
So we have two comma one over here.
Now to find the value for two comma one.
Again we have two options exclude and include.
Exclude is three comma one.
We just increment cur and prev stays the same.
And this over here will return zero because three is greater than the last valid index which is two.
So now that's the exclude branch.
Now in the include branch we are considering to include the element at index two which has a value three.
And the previous included element is the element at index one which has a value two.
Now three is greater than two.
So therefore we can include.
So when we include we have to do plus one.
So include is equal to one plus three comma two.
So this call over here is three comma two.
Now three comma two will return zero.
And the include branch becomes one plus zero which is equal to one.
Now between 0 and 1 the greater value is one.
So this call over here will return one.
And then we have to do plus one over here.
So for this call include becomes one plus one which is equal to two.
So exclude is one and include is two.
So this call over here will return the maximum between these two which is equal to two.
And then we have to add one to it.
So the include branch for this call is equal to three.
So exclude is two and include is three.
And the maximum between these two is equal to three.
And that's why the length of the longest increasing subsequence for this problem over here is three
itself, which is to include all the three elements.
So this is the recursion tree for the list question.
Now if this value over here was less than, let's say two, then when we were considering to include
the value at index two with the previous index one, we would not include it, right?
So before we go ahead and always calculate include we have to do that check.
And if you are not able to include it we have to initially set include to zero.
Now we will take a look at that in the code where we go ahead and write the code for this.
But over here we have completed to draw the recursion tree for the alias question.