1
00:00:00,910 --> 00:00:02,950
Hey there and welcome back.

2
00:00:03,070 --> 00:00:10,240
Let's now proceed and draw the recursion tree for the approach that we have discussed for solving the

3
00:00:10,240 --> 00:00:11,350
Liz question.

4
00:00:11,440 --> 00:00:17,230
Now for this, we will be writing a function that we will be recursively calling.

5
00:00:17,260 --> 00:00:20,230
Now let's say that function is called Liz.

6
00:00:20,260 --> 00:00:22,120
Now to this function.

7
00:00:22,120 --> 00:00:29,590
At every point we would have to pass the index that is being currently considered for including in the

8
00:00:29,590 --> 00:00:30,820
subsequence at hand.

9
00:00:30,850 --> 00:00:32,290
So let's call that curr.

10
00:00:32,290 --> 00:00:41,050
And we also would have to pass the index of the element that was previously included in the subsequence

11
00:00:41,050 --> 00:00:41,680
at hand.

12
00:00:41,680 --> 00:00:43,480
So that's curr and prev.

13
00:00:43,510 --> 00:00:50,380
Now this is required because to decide whether we can include the element at index curr in the subsequence

14
00:00:50,380 --> 00:00:57,910
at hand, we would need to know whether the value of the element at this index is greater than the value

15
00:00:57,910 --> 00:01:04,690
at this index over here, because the question asks us to develop a strictly increasing subsequence.

16
00:01:04,690 --> 00:01:15,460
So Liz Curr prev will return the longest increasing subsequence starting at index ker to the right with

17
00:01:15,460 --> 00:01:19,030
values greater than the value at index prev.

18
00:01:19,090 --> 00:01:25,630
So for example, if again this is the array which is given to us, which is one, two, three, the

19
00:01:25,630 --> 00:01:28,180
indices are zero, one and two.

20
00:01:28,180 --> 00:01:34,360
Let's say at one point curr was equal to one and let's say prev is equal to zero.

21
00:01:34,360 --> 00:01:41,950
This means that the previously included value in the subsequence is the value at index zero, which

22
00:01:41,950 --> 00:01:49,300
is one, and the value that we are considering for inclusion is the value at index one, which is this

23
00:01:49,300 --> 00:01:50,200
value over here.

24
00:01:50,200 --> 00:01:57,730
And what this call will return is the length of the longest increasing subsequence starting at index

25
00:01:57,730 --> 00:01:58,120
curr.

26
00:01:58,210 --> 00:02:03,370
So it will take into consideration elements starting at this index to the right.

27
00:02:03,370 --> 00:02:04,870
So that's two and three.

28
00:02:05,910 --> 00:02:15,900
So this call over here will return the longest increasing subsequence of this array over here with values.

29
00:02:16,720 --> 00:02:23,110
Greater than one because one is the value at the previous index, which is index zero.

30
00:02:23,110 --> 00:02:24,400
So you have one over here.

31
00:02:24,400 --> 00:02:27,520
So this is what l I s curve prev will return.

32
00:02:27,520 --> 00:02:35,350
And also remember that when we start off with the function calls initially we would have nothing added

33
00:02:35,350 --> 00:02:37,300
to a subsequence that we are considering.

34
00:02:37,300 --> 00:02:41,620
And at that point we will set prev to equal minus one.

35
00:02:41,620 --> 00:02:49,750
So if prev is not equal to minus one, it means that the subsequence which we are considering already

36
00:02:49,750 --> 00:02:58,300
has some elements included, and in that case, values greater than the value at index prev only can

37
00:02:58,300 --> 00:03:00,400
be included to the subsequence.

38
00:03:00,400 --> 00:03:00,970
All right.

39
00:03:00,970 --> 00:03:07,030
So keeping this in mind let's proceed and draw the recursion tree for this question.

40
00:03:07,570 --> 00:03:10,330
So initially we have our array.

41
00:03:10,330 --> 00:03:11,560
That's 123.

42
00:03:11,560 --> 00:03:14,290
The indices are zero one and two.

43
00:03:14,320 --> 00:03:17,590
So we make a call to the list function.

44
00:03:17,590 --> 00:03:23,830
And we pass index cur at this point, which is zero because we have decided to go from zero to the last

45
00:03:23,830 --> 00:03:24,340
index.

46
00:03:24,340 --> 00:03:26,140
So cur would be equal to zero.

47
00:03:26,140 --> 00:03:32,770
And because nothing has been included in the subsequence so far, we set prev to equal minus one.

48
00:03:32,770 --> 00:03:40,090
Now we have two choices with respect to this element at index zero, which is either to exclude this

49
00:03:40,090 --> 00:03:42,790
element or include this element.

50
00:03:42,790 --> 00:03:46,960
If we choose to exclude this element, we have to increment cur.

51
00:03:46,960 --> 00:03:53,560
So cur becomes one, but prev stays the same because nothing again has been included as of now.

52
00:03:53,560 --> 00:03:57,370
Over here nothing was included and we just excluded this element.

53
00:03:57,370 --> 00:03:59,470
So still nothing is included.

54
00:03:59,470 --> 00:04:03,280
So prev does not change and prev is still minus one.

55
00:04:03,280 --> 00:04:04,540
Again over here.

56
00:04:04,540 --> 00:04:10,240
When we are considering the element at index one, we have two choices which is to exclude this element

57
00:04:10,240 --> 00:04:12,040
or include this element.

58
00:04:12,040 --> 00:04:18,670
Now over here, when we exclude this element, we proceed to index two and prev does not change.

59
00:04:18,670 --> 00:04:20,200
Prev is still minus one.

60
00:04:20,200 --> 00:04:27,220
Again we have two choices to exclude the element at index two or include the element over here and when

61
00:04:27,220 --> 00:04:31,630
we exclude it curve becomes three and prev stays minus one.

62
00:04:31,630 --> 00:04:35,350
And this call over here will return the value zero.

63
00:04:35,350 --> 00:04:40,660
Because note is that cur is now greater than the last index which was two.

64
00:04:40,660 --> 00:04:45,730
So we have hit the base case and therefore we will just return zero over here.

65
00:04:46,240 --> 00:04:51,910
Then we'll go down this branch over here, which is to include the element at index two.

66
00:04:51,910 --> 00:04:59,020
And when we do that cur again will become three, but prev will become two because the element at index

67
00:04:59,020 --> 00:05:00,430
two was included.

68
00:05:00,430 --> 00:05:02,440
So this value becomes prev.

69
00:05:02,530 --> 00:05:07,960
Now in this call again we will return zero because we have hit the base case over here because this

70
00:05:07,960 --> 00:05:11,470
is three which is greater than two which is the last valid index.

71
00:05:11,470 --> 00:05:16,270
But because we have included one element we have to add one to this.

72
00:05:16,270 --> 00:05:18,820
So this over here will return zero.

73
00:05:18,820 --> 00:05:23,470
And finally include will become one plus zero which is equal to one.

74
00:05:23,470 --> 00:05:27,820
So we get exclude over here as zero and include as one.

75
00:05:27,820 --> 00:05:33,790
And the greater value between exclude and include between 0 and 1 is one.

76
00:05:33,790 --> 00:05:38,500
And therefore this call over here will return the value one.

77
00:05:39,690 --> 00:05:42,210
All right, so we're done with this branch over here.

78
00:05:42,210 --> 00:05:44,100
Now we go down this branch.

79
00:05:44,100 --> 00:05:47,160
So we were at one comma minus one.

80
00:05:47,160 --> 00:05:53,850
And because we are including this, whatever we have over here, we have to again increment the value

81
00:05:53,850 --> 00:05:54,390
of cur.

82
00:05:54,390 --> 00:05:55,800
So cur becomes two.

83
00:05:55,800 --> 00:06:02,550
And prev also changes from minus one to this value, which is the latest value which was included.

84
00:06:02,550 --> 00:06:09,660
Now again remember before we include we have to check whether either nothing has been included and which

85
00:06:09,660 --> 00:06:10,590
is the case over here.

86
00:06:10,590 --> 00:06:12,810
We have prev to equal minus one.

87
00:06:12,810 --> 00:06:15,360
So nothing has been included as of now.

88
00:06:15,360 --> 00:06:17,880
And therefore we can go ahead and include this value.

89
00:06:17,880 --> 00:06:24,840
If this was not the case then we would have to check that the value at the index curve is greater than

90
00:06:24,840 --> 00:06:26,490
the value at index prev.

91
00:06:26,490 --> 00:06:30,570
So over here, because prev is minus one we can go ahead and include this.

92
00:06:30,570 --> 00:06:33,180
So we have two comma one over here.

93
00:06:33,180 --> 00:06:38,730
And because we have included one element we have to do a plus one over here.

94
00:06:38,730 --> 00:06:41,010
Two whatever gets returned over here.

95
00:06:41,010 --> 00:06:42,630
So we have two comma one.

96
00:06:42,630 --> 00:06:48,690
And again we have two choices with respect to the element at index two, which is to either exclude

97
00:06:48,690 --> 00:06:50,040
it or include it.

98
00:06:50,040 --> 00:06:52,500
When we exclude it we get three comma one.

99
00:06:52,500 --> 00:06:53,850
So prev does not change.

100
00:06:53,850 --> 00:06:58,080
And because this is three which is greater than two, this returns zero.

101
00:06:58,080 --> 00:07:05,100
Now when it comes to including this, we are considering the element at index two which has a value

102
00:07:05,100 --> 00:07:05,880
of three.

103
00:07:05,880 --> 00:07:11,700
And the previously included element was the element at index one, which has a value of two.

104
00:07:11,700 --> 00:07:15,570
Now, because three is greater than two, we can include this.

105
00:07:15,570 --> 00:07:22,260
So in this branch when we include it, include becomes one plus this call over here which is three comma

106
00:07:22,260 --> 00:07:22,680
two.

107
00:07:22,680 --> 00:07:30,150
Notice that prev has changed from 1 to 2 because two is the most recently added element to the subsequence.

108
00:07:30,150 --> 00:07:35,910
Now three comma two again will return zero because three is greater than the last valid index, which

109
00:07:35,910 --> 00:07:36,420
is two.

110
00:07:36,420 --> 00:07:43,740
So this also will return zero and the include branch will become one plus zero, which is equal to one.

111
00:07:43,740 --> 00:07:48,420
So over here exclude is equal to zero and include becomes one.

112
00:07:48,420 --> 00:07:53,940
So two comma one will return the value one which is the greater among these two.

113
00:07:55,420 --> 00:08:01,870
So notice over here because over here we were including to this one we have to add one.

114
00:08:01,870 --> 00:08:05,140
So the include branch over here becomes equal to two.

115
00:08:05,140 --> 00:08:07,180
And exclude is equal to one.

116
00:08:07,180 --> 00:08:10,360
And between 1 and 2 the greater value is two.

117
00:08:10,390 --> 00:08:13,570
So this over here will return the value two.

118
00:08:14,180 --> 00:08:16,250
And we're done with this branch.

119
00:08:16,250 --> 00:08:18,050
Now let's go down this branch.

120
00:08:18,050 --> 00:08:21,620
So cur is equal to zero and prev is equal to minus one.

121
00:08:21,620 --> 00:08:27,830
And because prev is equal to minus one, nothing has been as of now included in the subsequence at hand.

122
00:08:27,830 --> 00:08:31,880
And we can go ahead and include the value at index zero.

123
00:08:31,880 --> 00:08:34,970
So when we include we have to do plus one.

124
00:08:34,970 --> 00:08:42,260
So include is equal to one plus this recursive call over here where cur has been incremented and prev

125
00:08:42,290 --> 00:08:46,640
has been changed to this value over here because we have included it.

126
00:08:46,640 --> 00:08:50,630
So the latest included element is at index zero.

127
00:08:50,630 --> 00:08:58,760
Now to solve the call where we are passing one comma zero to the loss function, we have again two possibilities.

128
00:08:58,760 --> 00:09:05,330
That is either to exclude the element at index one or include the element at index one.

129
00:09:05,330 --> 00:09:12,650
Now, when we exclude the element, we just have to increment cur and prev stays as it is, so the call

130
00:09:12,650 --> 00:09:17,000
becomes two comma zero, where car is two and prev is still zero.

131
00:09:17,000 --> 00:09:21,560
And then to solve two comma zero we again have two possibilities.

132
00:09:21,560 --> 00:09:26,720
We have exclude and include and in the exclude branch again we increment cur.

133
00:09:26,720 --> 00:09:30,260
So we get three over here and prev stays the same which is zero.

134
00:09:30,260 --> 00:09:36,050
Now three comma zero will return zero because this three is greater than this two over here which is

135
00:09:36,050 --> 00:09:37,490
the last valid index.

136
00:09:37,490 --> 00:09:41,240
So we have hit the base case and we return zero over here.

137
00:09:42,040 --> 00:09:48,430
Now in the include branch, we are considering to include the element at index two, and the previously

138
00:09:48,430 --> 00:09:52,990
included element is the element at index zero, which has a value of one.

139
00:09:52,990 --> 00:09:59,710
So the element at index two, which is three, is greater than one, and therefore we can include this.

140
00:09:59,710 --> 00:10:02,800
So when we include it we have to add one.

141
00:10:02,800 --> 00:10:09,670
So include is equal to one plus the recursive call where cur is equal to three and prev is changed to

142
00:10:09,670 --> 00:10:11,620
this value over here which is two.

143
00:10:11,620 --> 00:10:17,470
So three comma two will again return zero because three is greater than this two over here.

144
00:10:18,100 --> 00:10:18,550
Right.

145
00:10:18,550 --> 00:10:20,050
So we have hit the base case.

146
00:10:20,050 --> 00:10:26,320
So this over here will return zero and include becomes one plus zero which is equal to one.

147
00:10:26,710 --> 00:10:29,080
So exclude is zero and include is one.

148
00:10:29,080 --> 00:10:31,210
So the greater among these two is one.

149
00:10:31,210 --> 00:10:35,290
And therefore this call over here will return the value one.

150
00:10:35,680 --> 00:10:37,390
And then we come down over here.

151
00:10:37,420 --> 00:10:44,950
Now what's this problem over here we have the element at index zero as the previous included element

152
00:10:44,950 --> 00:10:46,090
which has a value one.

153
00:10:46,090 --> 00:10:51,310
And we are considering to include the element at index one which has a value two.

154
00:10:51,310 --> 00:10:53,050
Now two is greater than one.

155
00:10:53,050 --> 00:10:55,180
Therefore we can include.

156
00:10:55,180 --> 00:10:58,810
So when we include we have to do plus one.

157
00:10:58,810 --> 00:11:05,740
So include is equal to one plus the recursive call where cur is equal to two and prev is equal to this

158
00:11:05,740 --> 00:11:06,010
one.

159
00:11:06,010 --> 00:11:06,670
Over here.

160
00:11:07,180 --> 00:11:09,340
So we have two comma one over here.

161
00:11:09,340 --> 00:11:11,830
Now to find the value for two comma one.

162
00:11:11,830 --> 00:11:15,070
Again we have two options exclude and include.

163
00:11:15,070 --> 00:11:16,630
Exclude is three comma one.

164
00:11:16,630 --> 00:11:19,930
We just increment cur and prev stays the same.

165
00:11:19,930 --> 00:11:25,480
And this over here will return zero because three is greater than the last valid index which is two.

166
00:11:25,720 --> 00:11:28,150
So now that's the exclude branch.

167
00:11:28,150 --> 00:11:34,150
Now in the include branch we are considering to include the element at index two which has a value three.

168
00:11:34,150 --> 00:11:39,280
And the previous included element is the element at index one which has a value two.

169
00:11:39,280 --> 00:11:41,320
Now three is greater than two.

170
00:11:41,350 --> 00:11:43,390
So therefore we can include.

171
00:11:43,390 --> 00:11:46,720
So when we include we have to do plus one.

172
00:11:46,720 --> 00:11:50,890
So include is equal to one plus three comma two.

173
00:11:50,920 --> 00:11:52,840
So this call over here is three comma two.

174
00:11:52,870 --> 00:11:55,120
Now three comma two will return zero.

175
00:11:55,120 --> 00:11:59,380
And the include branch becomes one plus zero which is equal to one.

176
00:11:59,380 --> 00:12:02,410
Now between 0 and 1 the greater value is one.

177
00:12:02,410 --> 00:12:04,990
So this call over here will return one.

178
00:12:04,990 --> 00:12:07,240
And then we have to do plus one over here.

179
00:12:07,240 --> 00:12:12,370
So for this call include becomes one plus one which is equal to two.

180
00:12:12,400 --> 00:12:14,740
So exclude is one and include is two.

181
00:12:14,770 --> 00:12:19,870
So this call over here will return the maximum between these two which is equal to two.

182
00:12:19,870 --> 00:12:21,880
And then we have to add one to it.

183
00:12:21,880 --> 00:12:25,420
So the include branch for this call is equal to three.

184
00:12:25,420 --> 00:12:28,300
So exclude is two and include is three.

185
00:12:28,300 --> 00:12:31,360
And the maximum between these two is equal to three.

186
00:12:31,360 --> 00:12:37,960
And that's why the length of the longest increasing subsequence for this problem over here is three

187
00:12:37,960 --> 00:12:41,110
itself, which is to include all the three elements.

188
00:12:41,110 --> 00:12:44,680
So this is the recursion tree for the list question.

189
00:12:44,680 --> 00:12:51,370
Now if this value over here was less than, let's say two, then when we were considering to include

190
00:12:51,370 --> 00:12:55,750
the value at index two with the previous index one, we would not include it, right?

191
00:12:55,750 --> 00:13:01,090
So before we go ahead and always calculate include we have to do that check.

192
00:13:01,090 --> 00:13:05,290
And if you are not able to include it we have to initially set include to zero.

193
00:13:05,290 --> 00:13:09,610
Now we will take a look at that in the code where we go ahead and write the code for this.

194
00:13:09,610 --> 00:13:15,640
But over here we have completed to draw the recursion tree for the alias question.