Let's now get into the code and implement the recursive solution for solving the Liz question.
Okay, so this is going to be a recursive solution.
And we will be using a helper function.
Let me just call it helper itself.
And to this function we will be passing the current index that we are considering whether to include
in the subsequence or not.
And we will also have to pass the previous index which was included in the subsequence that we are building.
Okay, so let's call that pref.
So these two have to be passed to the helper function.
And finally over here we'll have to call the helper function.
And we will be writing this helper function in a way that it will return the length of the longest increasing
subsequence.
And because we get it from the helper function, we can directly just return it over here.
And when we call the helper function for the first time, the first parameters that we pass to it will
depend on how we write the recursive solution.
Now we can write a recursive solution, either going from zero to the last index, or we can start at
the last index and go to zero.
But over here we are going to start from zero.
So let's pass cur as zero and pref as minus one because nothing has been added to the subsequence as
of now okay.
Now let's go ahead and write the details of the helper function.
So over here I'll be writing the base case as well as the recursive case.
Now when it comes to the base case, we have discussed that you can think of it as either being the
last valid input or the first invalid input.
Now, because we are going from zero to the last index of the input array, and let's say that the length
of the input array is equal to n.
So we would have hit the first invalid input.
If cur is greater than equal to n okay or greater than n minus one or greater than equal to n.
Because the last valid index in this case would be n minus one.
And if we do hit the base case, we can just return zero because there are no more numbers.
Right?
We have gone beyond the last valid index of the num array.
Now if this is not the case we proceed to the recursive case.
And over here we will have to calculate exclude.
And we'll have to calculate include okay.
And then finally we will be just returning the maximum between these two.
So that's how we are going to approach this okay.
All right.
Now to calculate the exclude value.
Again that's just the longest increasing subsequence.
If we exclude the value at the current index.
And to do that we will just recursively call the helper function again.
And car would be passed as car plus one because we are avoiding or excluding the current element, and
we are moving to the next index.
And because nothing has been added to the subsequence, prev remains.
Whatever we got over here.
So that's going to be private self and that's it.
So this will give us the exclude value.
Now let's initialize the include value to zero because we need some include value because we are using
it over here.
And we would not always be able to include the element at index curve okay.
We can include the element at index curve only if it is greater than the last added value.
Okay.
So let's go ahead and check whether we can include the element at index curve.
So for us to be able to include the element either prev has to be equal to minus one, which means that
nothing has been added to the subsequence as of now.
And therefore we can add the element at index curve or if numb's at curve is greater than numb's at
prev.
Okay, so if the element at index curve is greater than the element at index prev, then we will be
able to add that particular element to the subsequence we are considering.
And therefore, if either of these are true, then we can say that include is equal to one plus whatever
we get from the recursive call to the helper function with curve plus one and curve as the input parameters.
Now again we have one plus over here we have this one over here because one element has been added to
the subsequence right which is the element at index curve.
And over here we are moving to the next index which is curve plus one.
And prev has been changed to cur because cur is now the most recently added element, right.
The element at index curve is the most recently added element to the subsequence.
So that's why prev has to be changed to cur over here.
And that's it.
This should take care of solving this question.
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 recursive approach for solving the list.