1
00:00:00,360 --> 00:00:01,500
Welcome back.

2
00:00:01,710 --> 00:00:09,480
Let's now do a dry run of the approach that we're going to take to solve this question, using the bottom

3
00:00:09,480 --> 00:00:12,390
up approach with just a one dimensional array.

4
00:00:12,420 --> 00:00:16,590
So let's say this is the array which is given to us as the input.

5
00:00:16,800 --> 00:00:20,700
And this is the DP array that we have created.

6
00:00:20,700 --> 00:00:25,560
And we have one place for every index in the array which is given to us.

7
00:00:25,560 --> 00:00:31,050
So the indices over here are zero, one, two, three, four, five and six.

8
00:00:31,050 --> 00:00:35,580
And over here also we have 0123456.

9
00:00:35,580 --> 00:00:41,400
Now this is the relation recurrence relation that we have discussed previously which can be used to

10
00:00:41,400 --> 00:00:42,930
fill this DP table.

11
00:00:42,930 --> 00:00:45,480
We will see more of this in action soon.

12
00:00:45,810 --> 00:00:54,060
Now to start with over here I can fill the value in every cell to be equal to one, because I could

13
00:00:54,060 --> 00:00:59,640
form an increasing subsequence by just including the element at hand.

14
00:00:59,640 --> 00:01:07,140
Remember, every cell over here represents the length of the longest increasing subsequence, where

15
00:01:07,140 --> 00:01:10,620
the element at that particular index is included.

16
00:01:10,650 --> 00:01:15,870
Now, if I were to just take that element alone, I get a length of one.

17
00:01:15,870 --> 00:01:20,640
And that's why we can initialize the values over here as equal to one.

18
00:01:21,030 --> 00:01:30,480
Now again dp at index I is the length of the longest increasing subsequence that has the element at

19
00:01:30,480 --> 00:01:31,830
index I included.

20
00:01:31,830 --> 00:01:36,420
So this is going to be the last element in the increasing subsequence.

21
00:01:36,420 --> 00:01:42,360
And the length of that increasing subsequence is what we will fill in each of these cells.

22
00:01:42,360 --> 00:01:46,530
So to start with, we have filled every cell over here with the value one.

23
00:01:46,530 --> 00:01:48,840
Now let's again write the indices over here.

24
00:01:48,840 --> 00:01:50,910
So it goes from 0 to 6.

25
00:01:50,940 --> 00:01:54,990
Now first we will have another pointer let's say I.

26
00:01:54,990 --> 00:01:58,680
And it's going to take the values from one up to six.

27
00:02:00,570 --> 00:02:01,260
Okay.

28
00:02:01,260 --> 00:02:04,800
And for each value of I when I is.

29
00:02:04,800 --> 00:02:10,290
For example, one J will take all the previous indices as its value.

30
00:02:10,290 --> 00:02:12,480
So initially I is equal to one.

31
00:02:12,480 --> 00:02:20,460
So j will just take the value zero and we will check whether the value at index one which is two, whether

32
00:02:20,460 --> 00:02:23,640
two is greater than the value at index zero which is one.

33
00:02:23,640 --> 00:02:26,040
So we see that two is greater than one.

34
00:02:26,040 --> 00:02:34,200
And therefore it means that this element can be added to the subsequence where we just have this element

35
00:02:34,200 --> 00:02:34,680
over here.

36
00:02:34,680 --> 00:02:36,270
And that's why we have one over here.

37
00:02:36,270 --> 00:02:41,820
Because this is just representing a subsequence where only one element is there.

38
00:02:41,820 --> 00:02:46,260
Now, because two is greater than one, we can add it to this subsequence.

39
00:02:46,590 --> 00:02:52,860
And this value over here becomes two because the subsequence now is one comma two.

40
00:02:52,860 --> 00:02:55,200
Now let's take a look at this over here.

41
00:02:55,200 --> 00:02:57,750
Now numb's at I that's equal to two.

42
00:02:57,750 --> 00:03:04,770
And two is greater than numb's at j which is equal to one, and dp at j which is equal to one plus one.

43
00:03:04,770 --> 00:03:07,920
So one plus one is greater than DP at I.

44
00:03:07,950 --> 00:03:10,200
So initially DP at I was one right.

45
00:03:10,200 --> 00:03:12,270
So one plus one is greater than one.

46
00:03:12,270 --> 00:03:14,910
So these two conditions are satisfied.

47
00:03:14,910 --> 00:03:20,100
That's why we will set DP at I to equal DP at j plus one.

48
00:03:20,100 --> 00:03:21,870
And again DP at j is one.

49
00:03:21,870 --> 00:03:24,090
So one plus one gives us two.

50
00:03:24,090 --> 00:03:26,610
And that's how we fill the value two over here.

51
00:03:26,610 --> 00:03:29,250
And again what's the meaning of this.

52
00:03:29,250 --> 00:03:36,270
This is over here two because the subsequence the longest increasing subsequence that can be formed

53
00:03:36,270 --> 00:03:42,870
including this element and considering these elements is one comma two and the length of one comma two

54
00:03:42,900 --> 00:03:44,100
is equal to two.

55
00:03:44,100 --> 00:03:45,570
And we fill that over here.

56
00:03:46,250 --> 00:03:47,360
Now we proceed.

57
00:03:47,360 --> 00:03:54,050
So I comes to the next value, which is equal to and j will take these two values.

58
00:03:54,050 --> 00:03:56,840
Initially j will take the value zero.

59
00:03:57,540 --> 00:04:03,990
So we'll have Jay over here and we will check whether the value over here, which is one, is one greater

60
00:04:03,990 --> 00:04:09,480
than the value at index zero, which is one, we see that one is not greater than one.

61
00:04:09,960 --> 00:04:12,300
And therefore Jay moves ahead.

62
00:04:13,110 --> 00:04:15,570
So j now is equal to one.

63
00:04:15,570 --> 00:04:17,340
And over here we have again one.

64
00:04:17,340 --> 00:04:18,900
And over here we have two.

65
00:04:18,900 --> 00:04:21,090
Now is one greater than two.

66
00:04:21,090 --> 00:04:23,100
No that's also not true.

67
00:04:23,100 --> 00:04:26,460
And therefore notice that nothing has been updated.

68
00:04:26,460 --> 00:04:28,200
And we move the value of I.

69
00:04:28,230 --> 00:04:32,280
Now when we say that nothing has been updated, what does it actually mean?

70
00:04:32,280 --> 00:04:39,000
It means that we can only form an increasing subsequence where there is just one element.

71
00:04:39,000 --> 00:04:40,680
So that's why we have one over here.

72
00:04:40,680 --> 00:04:46,920
And we are not able to add anything that came previously to the subsequence where one is the last added

73
00:04:46,920 --> 00:04:47,490
element.

74
00:04:47,730 --> 00:04:48,840
So that's it.

75
00:04:48,840 --> 00:04:52,590
Now again we move I and I becomes equal to three.

76
00:04:54,070 --> 00:04:57,340
And Jay will take the values from zero up to two.

77
00:04:57,550 --> 00:04:59,650
Initially, Jay will take the value zero.

78
00:04:59,650 --> 00:05:02,200
So I is three and Jay is zero.

79
00:05:02,200 --> 00:05:03,910
So that's these two indices.

80
00:05:03,910 --> 00:05:07,330
So we have the value four over here and the value one over here.

81
00:05:07,360 --> 00:05:10,630
Now we see that four is greater than one.

82
00:05:11,020 --> 00:05:18,460
Therefore yes we can add four to the subsequence which is represented over here and over here.

83
00:05:18,460 --> 00:05:19,330
Again that's this.

84
00:05:19,330 --> 00:05:20,260
This is true.

85
00:05:20,290 --> 00:05:26,980
Now what about this DP at Jay is one and one plus one is greater than DP at I which is one.

86
00:05:26,980 --> 00:05:34,600
So this means that we can update the value for dp at I to equal dp at j plus one, which is one plus

87
00:05:34,600 --> 00:05:34,900
one.

88
00:05:34,900 --> 00:05:39,880
So this value over here gets updated to one plus one which is equal to two.

89
00:05:39,910 --> 00:05:42,520
Now we will see why this is very important.

90
00:05:42,520 --> 00:05:42,880
All right.

91
00:05:42,880 --> 00:05:47,020
So again Jay moves ahead J becomes equal to one.

92
00:05:49,160 --> 00:05:51,470
Now again we compare the values.

93
00:05:51,470 --> 00:05:53,390
So over here we have the value four.

94
00:05:53,390 --> 00:05:55,160
And over here we have the value two.

95
00:05:55,190 --> 00:05:57,020
So four is greater than two.

96
00:05:58,240 --> 00:06:01,090
Therefore, this part over here is satisfied.

97
00:06:01,090 --> 00:06:05,440
And then we check whether DPR j plus one is greater than DPR I.

98
00:06:05,560 --> 00:06:09,310
So over here dpr j is equal to two.

99
00:06:10,240 --> 00:06:14,170
And two plus one is three, and three is greater than this two over here.

100
00:06:14,170 --> 00:06:14,620
Right.

101
00:06:14,620 --> 00:06:22,030
So we need to update the value of DP at I to equal dp at j which is now two plus one.

102
00:06:22,030 --> 00:06:26,410
And that's how this part over here gets changed to equal to three.

103
00:06:28,730 --> 00:06:29,060
Right.

104
00:06:29,060 --> 00:06:31,190
So that's why this is very important.

105
00:06:31,430 --> 00:06:38,780
So what we are doing is for every value of I, we are having another pointer J to iterate through all

106
00:06:38,780 --> 00:06:39,950
the previous values.

107
00:06:39,950 --> 00:06:46,550
And then this over here helps us to understand when it's time to actually update this, because we are

108
00:06:46,550 --> 00:06:50,390
able to form a larger subsequence or a longer subsequence.

109
00:06:50,420 --> 00:06:54,710
Over here we just had one element, but over here we have one comma two.

110
00:06:54,710 --> 00:07:01,280
And updating this actually means that if we add four to this, we just get one comma four.

111
00:07:01,280 --> 00:07:05,720
But if we add four to this subsequence, we get one comma two, comma four.

112
00:07:05,720 --> 00:07:11,030
And this is longer than this, which is why we have to update this to three.

113
00:07:11,730 --> 00:07:13,710
And then we move forward.

114
00:07:14,940 --> 00:07:18,960
So Jay takes the next value which is equal to two.

115
00:07:18,960 --> 00:07:21,810
And we are comparing these two values.

116
00:07:21,810 --> 00:07:24,450
Again we see that four is greater than one.

117
00:07:25,860 --> 00:07:34,350
But this criteria over here is not valid because DPI at J is just one, and one plus one is not greater

118
00:07:34,350 --> 00:07:37,080
than depee at I, which is already three.

119
00:07:37,110 --> 00:07:40,350
Therefore, we do not update the value over here.

120
00:07:40,350 --> 00:07:46,860
The implication of this is that over here the subsequence is just one, but the subsequence that we

121
00:07:46,860 --> 00:07:51,900
have considered to fill the value three over here is one, two and four.

122
00:07:51,900 --> 00:07:56,790
And by adding four to just this one over here, we will just get one comma four.

123
00:07:56,790 --> 00:08:02,430
And the length of this is not greater than the length of what we have already considered.

124
00:08:02,430 --> 00:08:06,480
So that's why we don't update the value over here and we move forward.

125
00:08:06,480 --> 00:08:09,000
So I now becomes equal to four.

126
00:08:09,360 --> 00:08:11,550
And then j is again equal to zero.

127
00:08:11,550 --> 00:08:14,070
Now we are considering these two values.

128
00:08:14,070 --> 00:08:16,170
We see that three is greater than one.

129
00:08:16,170 --> 00:08:19,650
And we see that one plus one is greater than two.

130
00:08:19,650 --> 00:08:22,740
And therefore we will update the value over here.

131
00:08:22,740 --> 00:08:24,930
And this will become equal to two.

132
00:08:25,470 --> 00:08:27,210
Again J moves forward.

133
00:08:28,070 --> 00:08:31,400
And over here we are comparing these two values.

134
00:08:31,400 --> 00:08:33,740
We see that three is greater than two.

135
00:08:33,740 --> 00:08:37,790
And we see that two plus one is greater than two.

136
00:08:38,090 --> 00:08:41,060
Therefore we update this two over here to three.

137
00:08:41,690 --> 00:08:43,250
Then we move forward again.

138
00:08:43,250 --> 00:08:44,690
So j is equal to two.

139
00:08:44,720 --> 00:08:46,700
We are comparing this three over here.

140
00:08:46,700 --> 00:08:48,020
And this value over here.

141
00:08:48,020 --> 00:08:50,180
We see that three is greater than one.

142
00:08:51,020 --> 00:08:56,480
But we see that one plus one is not greater than three.

143
00:08:56,660 --> 00:09:02,330
Therefore, we do not update the value for depee at I and j moves forward.

144
00:09:02,360 --> 00:09:08,900
Now we are comparing three and four, and three is not greater than four, so we don't do anything.

145
00:09:08,900 --> 00:09:10,100
And that's it.

146
00:09:10,100 --> 00:09:13,490
This loop ends and again we move I forward.

147
00:09:15,110 --> 00:09:17,000
Again, J takes the value zero.

148
00:09:17,990 --> 00:09:20,750
And we are comparing these two indices.

149
00:09:20,750 --> 00:09:25,520
So the value over here is for the value over here is one and four is greater than one.

150
00:09:26,220 --> 00:09:29,460
And one plus one is greater than one.

151
00:09:29,460 --> 00:09:31,710
So we can update this to two.

152
00:09:32,470 --> 00:09:34,120
And Jay moves forward.

153
00:09:35,110 --> 00:09:40,030
Now we are comparing four and two and notice that four is greater than two.

154
00:09:40,030 --> 00:09:45,340
And over here we have two and two plus one which is three is greater than two.

155
00:09:45,370 --> 00:09:48,970
Therefore we can update the value for dp at I.

156
00:09:49,000 --> 00:09:50,410
So this becomes three.

157
00:09:51,020 --> 00:09:52,970
And then Jay moves forward.

158
00:09:54,200 --> 00:10:00,110
Now we are comparing this and this four is greater than one again.

159
00:10:00,230 --> 00:10:04,250
But notice that one plus one is not greater than three.

160
00:10:04,250 --> 00:10:08,690
So we don't update the value for dp at I and j moves forward.

161
00:10:09,400 --> 00:10:12,310
Now we are comparing four and four.

162
00:10:12,340 --> 00:10:14,590
Now four is not greater than four.

163
00:10:14,590 --> 00:10:19,090
So we proceed because the question mentions strictly increasing.

164
00:10:19,090 --> 00:10:23,440
So we can't include equal values when building an increasing subsequence.

165
00:10:23,440 --> 00:10:27,370
So we move forward and we are comparing four and three.

166
00:10:27,370 --> 00:10:29,710
And yes four is greater than three.

167
00:10:29,710 --> 00:10:35,020
In this case right four is greater than three, and three plus one is greater than three.

168
00:10:35,320 --> 00:10:39,070
Therefore we will update this three to equal four.

169
00:10:39,070 --> 00:10:40,870
And we are done with this loop.

170
00:10:41,170 --> 00:10:45,760
Now we again move the value of I and j takes the value zero.

171
00:10:45,760 --> 00:10:50,410
And we are comparing five and one, and we see that five is greater than one.

172
00:10:50,410 --> 00:10:55,300
Therefore, over here we change this 1 to 1 plus one which is two.

173
00:10:55,900 --> 00:10:57,070
We move forward.

174
00:10:57,070 --> 00:10:59,350
Now j takes the value two.

175
00:10:59,380 --> 00:11:01,480
Now two plus one is three.

176
00:11:01,480 --> 00:11:06,400
That's greater than what we had over here which was two and five is greater than two as well.

177
00:11:06,400 --> 00:11:08,890
So we update this value to three.

178
00:11:09,470 --> 00:11:10,700
We move forward.

179
00:11:11,030 --> 00:11:12,920
Now five is greater than one.

180
00:11:12,920 --> 00:11:14,480
We're comparing these two values.

181
00:11:14,480 --> 00:11:18,830
Five is greater than one, but one plus one is not greater than three.

182
00:11:18,830 --> 00:11:20,960
So we don't change this value.

183
00:11:20,960 --> 00:11:23,000
And j again moves forward.

184
00:11:23,300 --> 00:11:25,580
Now we are comparing five and four.

185
00:11:25,580 --> 00:11:27,050
Five is greater than four.

186
00:11:27,050 --> 00:11:28,730
And over here we have three.

187
00:11:28,730 --> 00:11:30,920
And over here previously we had three.

188
00:11:30,920 --> 00:11:33,560
Three plus one is four which is greater than three.

189
00:11:33,560 --> 00:11:35,720
Therefore we update this to four.

190
00:11:35,720 --> 00:11:37,730
Now again we move forward.

191
00:11:37,730 --> 00:11:41,330
Now we are comparing five and three.

192
00:11:41,330 --> 00:11:42,980
Five is greater than three.

193
00:11:42,980 --> 00:11:44,540
And over here we have three.

194
00:11:44,540 --> 00:11:45,890
Three plus one is four.

195
00:11:45,890 --> 00:11:47,810
And over here we already have four.

196
00:11:47,810 --> 00:11:51,350
So three plus one which is four is not greater than four.

197
00:11:51,350 --> 00:11:53,000
So we don't update this.

198
00:11:53,000 --> 00:11:55,070
And j moves forward.

199
00:11:55,190 --> 00:11:56,930
Now j is equal to five.

200
00:11:56,930 --> 00:11:59,690
So we are comparing these two indices.

201
00:11:59,690 --> 00:12:01,040
So over here we have five.

202
00:12:01,040 --> 00:12:02,750
And over here we have the value four.

203
00:12:02,750 --> 00:12:04,850
Now five is greater than four.

204
00:12:04,850 --> 00:12:06,920
And over here the value was four right.

205
00:12:06,920 --> 00:12:09,260
For DP at five the value was four.

206
00:12:09,260 --> 00:12:11,900
Now four plus one is equal to five.

207
00:12:11,900 --> 00:12:15,260
And that's greater than four which is what we have over here.

208
00:12:15,260 --> 00:12:18,200
And therefore we update this to five.

209
00:12:20,720 --> 00:12:21,830
And we are done.

210
00:12:22,520 --> 00:12:25,040
So this is our DP table.

211
00:12:25,070 --> 00:12:31,340
Now notice that the values over here are 121334 and five.

212
00:12:31,340 --> 00:12:37,880
So let me write that over here 121334 and five.

213
00:12:37,880 --> 00:12:43,130
Now the answer would be not just the last element.

214
00:12:43,130 --> 00:12:48,800
The answer is whichever is the largest value in this subsequence.

215
00:12:48,800 --> 00:12:55,520
And it so happens that the largest value is at the last place, which is equal to five.

216
00:12:55,520 --> 00:12:56,990
Now this is important.

217
00:12:56,990 --> 00:12:58,040
Why is that so?

218
00:12:58,040 --> 00:13:05,780
Because again notice that if you just had these three elements one, two and one, and if you fill the

219
00:13:05,780 --> 00:13:08,060
DP table it would look like this.

220
00:13:08,330 --> 00:13:11,270
You will have one, you will have two and you will have one.

221
00:13:11,270 --> 00:13:13,430
So the answer is not this element.

222
00:13:13,430 --> 00:13:16,430
The answer in this case would be this two over here.

223
00:13:16,430 --> 00:13:24,860
So basically once we have constructed the DP table we need to identify the largest value which is there

224
00:13:24,860 --> 00:13:25,790
in this table.

225
00:13:25,790 --> 00:13:28,010
And that would give us the answer.