1
00:00:00,110 --> 00:00:06,260
Let's now get into the code and implement the recursive solution for solving the Liz question.

2
00:00:06,260 --> 00:00:09,110
Okay, so this is going to be a recursive solution.

3
00:00:09,110 --> 00:00:11,480
And we will be using a helper function.

4
00:00:11,480 --> 00:00:13,760
Let me just call it helper itself.

5
00:00:13,760 --> 00:00:19,640
And to this function we will be passing the current index that we are considering whether to include

6
00:00:19,640 --> 00:00:21,530
in the subsequence or not.

7
00:00:21,530 --> 00:00:28,640
And we will also have to pass the previous index which was included in the subsequence that we are building.

8
00:00:28,640 --> 00:00:30,320
Okay, so let's call that pref.

9
00:00:30,320 --> 00:00:33,290
So these two have to be passed to the helper function.

10
00:00:33,290 --> 00:00:36,440
And finally over here we'll have to call the helper function.

11
00:00:36,440 --> 00:00:43,190
And we will be writing this helper function in a way that it will return the length of the longest increasing

12
00:00:43,190 --> 00:00:43,940
subsequence.

13
00:00:43,940 --> 00:00:49,010
And because we get it from the helper function, we can directly just return it over here.

14
00:00:49,010 --> 00:00:54,770
And when we call the helper function for the first time, the first parameters that we pass to it will

15
00:00:54,770 --> 00:00:57,140
depend on how we write the recursive solution.

16
00:00:57,140 --> 00:01:03,380
Now we can write a recursive solution, either going from zero to the last index, or we can start at

17
00:01:03,380 --> 00:01:05,270
the last index and go to zero.

18
00:01:05,270 --> 00:01:07,910
But over here we are going to start from zero.

19
00:01:07,910 --> 00:01:15,920
So let's pass cur as zero and pref as minus one because nothing has been added to the subsequence as

20
00:01:15,920 --> 00:01:16,940
of now okay.

21
00:01:16,940 --> 00:01:20,270
Now let's go ahead and write the details of the helper function.

22
00:01:20,270 --> 00:01:26,420
So over here I'll be writing the base case as well as the recursive case.

23
00:01:27,830 --> 00:01:34,100
Now when it comes to the base case, we have discussed that you can think of it as either being the

24
00:01:34,100 --> 00:01:37,940
last valid input or the first invalid input.

25
00:01:37,940 --> 00:01:43,910
Now, because we are going from zero to the last index of the input array, and let's say that the length

26
00:01:43,910 --> 00:01:46,340
of the input array is equal to n.

27
00:01:47,150 --> 00:01:51,920
So we would have hit the first invalid input.

28
00:01:51,920 --> 00:01:58,610
If cur is greater than equal to n okay or greater than n minus one or greater than equal to n.

29
00:01:58,610 --> 00:02:02,330
Because the last valid index in this case would be n minus one.

30
00:02:02,330 --> 00:02:07,850
And if we do hit the base case, we can just return zero because there are no more numbers.

31
00:02:07,850 --> 00:02:08,060
Right?

32
00:02:08,060 --> 00:02:10,970
We have gone beyond the last valid index of the num array.

33
00:02:11,240 --> 00:02:15,320
Now if this is not the case we proceed to the recursive case.

34
00:02:15,320 --> 00:02:18,980
And over here we will have to calculate exclude.

35
00:02:19,370 --> 00:02:22,310
And we'll have to calculate include okay.

36
00:02:22,310 --> 00:02:27,380
And then finally we will be just returning the maximum between these two.

37
00:02:27,410 --> 00:02:30,110
So that's how we are going to approach this okay.

38
00:02:32,090 --> 00:02:32,780
All right.

39
00:02:32,780 --> 00:02:36,110
Now to calculate the exclude value.

40
00:02:36,320 --> 00:02:39,680
Again that's just the longest increasing subsequence.

41
00:02:39,680 --> 00:02:43,310
If we exclude the value at the current index.

42
00:02:43,310 --> 00:02:47,060
And to do that we will just recursively call the helper function again.

43
00:02:47,720 --> 00:02:54,140
And car would be passed as car plus one because we are avoiding or excluding the current element, and

44
00:02:54,140 --> 00:02:55,670
we are moving to the next index.

45
00:02:55,670 --> 00:03:00,020
And because nothing has been added to the subsequence, prev remains.

46
00:03:00,020 --> 00:03:01,760
Whatever we got over here.

47
00:03:01,760 --> 00:03:03,950
So that's going to be private self and that's it.

48
00:03:03,950 --> 00:03:06,230
So this will give us the exclude value.

49
00:03:06,230 --> 00:03:12,620
Now let's initialize the include value to zero because we need some include value because we are using

50
00:03:12,620 --> 00:03:13,340
it over here.

51
00:03:13,340 --> 00:03:18,890
And we would not always be able to include the element at index curve okay.

52
00:03:18,890 --> 00:03:25,220
We can include the element at index curve only if it is greater than the last added value.

53
00:03:25,220 --> 00:03:25,550
Okay.

54
00:03:25,550 --> 00:03:29,510
So let's go ahead and check whether we can include the element at index curve.

55
00:03:29,510 --> 00:03:36,230
So for us to be able to include the element either prev has to be equal to minus one, which means that

56
00:03:36,230 --> 00:03:38,660
nothing has been added to the subsequence as of now.

57
00:03:38,660 --> 00:03:47,510
And therefore we can add the element at index curve or if numb's at curve is greater than numb's at

58
00:03:47,510 --> 00:03:48,110
prev.

59
00:03:48,110 --> 00:03:54,230
Okay, so if the element at index curve is greater than the element at index prev, then we will be

60
00:03:54,230 --> 00:03:58,070
able to add that particular element to the subsequence we are considering.

61
00:03:58,070 --> 00:04:05,420
And therefore, if either of these are true, then we can say that include is equal to one plus whatever

62
00:04:05,420 --> 00:04:12,260
we get from the recursive call to the helper function with curve plus one and curve as the input parameters.

63
00:04:12,260 --> 00:04:17,630
Now again we have one plus over here we have this one over here because one element has been added to

64
00:04:17,630 --> 00:04:20,600
the subsequence right which is the element at index curve.

65
00:04:20,600 --> 00:04:24,470
And over here we are moving to the next index which is curve plus one.

66
00:04:24,470 --> 00:04:31,400
And prev has been changed to cur because cur is now the most recently added element, right.

67
00:04:31,400 --> 00:04:36,170
The element at index curve is the most recently added element to the subsequence.

68
00:04:36,170 --> 00:04:38,600
So that's why prev has to be changed to cur over here.

69
00:04:38,600 --> 00:04:39,560
And that's it.

70
00:04:39,560 --> 00:04:42,050
This should take care of solving this question.

71
00:04:42,050 --> 00:04:45,980
Now let's go ahead and run this code and see if it's passing all the test cases.

72
00:04:47,500 --> 00:04:49,330
And you can see that it's working.

73
00:04:49,330 --> 00:04:50,920
It's passing all the test cases.

74
00:04:50,920 --> 00:04:54,100
So this is the recursive approach for solving the list.