1
00:00:00,110 --> 00:00:00,920
Welcome back.

2
00:00:00,920 --> 00:00:07,010
Let's now get into the code for implementing the tabulation approach for solving the Liz question.

3
00:00:07,010 --> 00:00:11,960
And over here we are discussing the tabulation approach using a 2D DP array.

4
00:00:11,960 --> 00:00:15,950
And we will discuss the approach using a 1D array in a later video.

5
00:00:15,950 --> 00:00:21,500
Now again, I have quickly drawn this out over here so that we can visualize what we're going to implement

6
00:00:21,500 --> 00:00:21,950
over here.

7
00:00:21,950 --> 00:00:24,050
So we have this 2D array.

8
00:00:24,050 --> 00:00:27,080
And let's say this is the Nums array which is given to us.

9
00:00:27,080 --> 00:00:32,390
Notice that the values for pref go from minus one up to one okay.

10
00:00:32,390 --> 00:00:34,700
So again minus one means nothing.

11
00:00:34,700 --> 00:00:36,140
And then zero and one.

12
00:00:36,140 --> 00:00:37,640
That's this zero and this one.

13
00:00:37,640 --> 00:00:43,160
Now to implement this or represent this in this DP array we will be adding one to it.

14
00:00:43,160 --> 00:00:45,230
So minus one will be changed to zero.

15
00:00:45,230 --> 00:00:48,830
Zero will be changed to one and one will be changed to two okay.

16
00:00:48,830 --> 00:00:50,330
And over here we have curr.

17
00:00:50,330 --> 00:00:53,720
And the values for curve span from zero up to two.

18
00:00:53,720 --> 00:00:59,330
And as we have discussed in the previous video these are the initial conditions that we need okay.

19
00:00:59,330 --> 00:01:01,700
So we will have zero field over here and here.

20
00:01:01,700 --> 00:01:05,960
And then we would just need to iterate over these cells right.

21
00:01:05,960 --> 00:01:07,700
We would first start over here.

22
00:01:07,700 --> 00:01:08,900
Then we come over here.

23
00:01:08,900 --> 00:01:12,140
Then we come over here and then here and then here and then here.

24
00:01:12,140 --> 00:01:15,470
And finally this is where we would be getting our answer.

25
00:01:15,470 --> 00:01:21,950
Because notice this problem over here represents the scenario where you can include elements starting

26
00:01:21,950 --> 00:01:24,380
and index zero and to the right of it.

27
00:01:24,380 --> 00:01:26,990
So in fact you can include all of the elements.

28
00:01:26,990 --> 00:01:30,290
And prev over here is equal to minus one.

29
00:01:30,290 --> 00:01:33,950
Which means that nothing has been added to the subsequence that we are building.

30
00:01:33,950 --> 00:01:36,980
And that is the original problem which has been given to us.

31
00:01:36,980 --> 00:01:37,430
All right.

32
00:01:37,460 --> 00:01:39,170
Now let's get into the code.

33
00:01:40,790 --> 00:01:45,620
So let's say n is the length of the nums array which is given to us.

34
00:01:46,430 --> 00:01:54,530
And let's create a 2D dp array which will have n plus one rows and n plus one columns.

35
00:01:54,860 --> 00:01:55,340
Okay.

36
00:02:00,400 --> 00:02:05,530
All right then over here we'll have array and plus one because we want n plus one columns.

37
00:02:05,530 --> 00:02:10,570
And what we will do is we will fill every cell in the DP array with the value zero.

38
00:02:10,570 --> 00:02:13,810
And this will take care of the initialization requirement.

39
00:02:13,810 --> 00:02:14,170
Right.

40
00:02:14,170 --> 00:02:19,360
Because we are filling every cell with the value zero automatically, these cells also will be filled

41
00:02:19,360 --> 00:02:20,350
with the value zero.

42
00:02:20,350 --> 00:02:23,590
And then we do not need to explicitly write code for that.

43
00:02:24,310 --> 00:02:24,790
All right.

44
00:02:24,790 --> 00:02:25,840
So let's get back.

45
00:02:25,840 --> 00:02:30,160
Now let's iterate through the remaining cells again quickly pulling up our drawing.

46
00:02:30,160 --> 00:02:33,700
Notice that we just need to iterate through these cells over here.

47
00:02:33,700 --> 00:02:38,500
So at this point I for example is equal to n minus one.

48
00:02:38,500 --> 00:02:42,100
And we will go till I is equal to zero okay.

49
00:02:42,100 --> 00:02:45,160
So from two up to zero two is n minus one.

50
00:02:45,160 --> 00:02:46,090
And this is zero.

51
00:02:46,090 --> 00:02:54,220
And for example when I is equal to n minus one notice that j takes the values from I up to zero.

52
00:02:54,220 --> 00:02:56,020
So that is what you can see over here right.

53
00:02:56,020 --> 00:03:03,010
So let's use that to build the nested for loops that we will need to iterate through these cells specifically

54
00:03:03,010 --> 00:03:03,430
okay.

55
00:03:03,430 --> 00:03:13,240
So I can say for let I is equal to n minus one I greater than or equal to zero I minus minus.

56
00:03:13,870 --> 00:03:23,110
And for let j is equal to I, j greater than or equal to zero j minus minus okay.

57
00:03:23,800 --> 00:03:24,220
All right.

58
00:03:24,220 --> 00:03:26,800
So these are the cells that we are going to visit over here.

59
00:03:26,800 --> 00:03:31,720
And for each of these combinations we will have to calculate exclude.

60
00:03:32,140 --> 00:03:34,720
And we'll have to calculate include okay.

61
00:03:34,720 --> 00:03:38,920
Now again let's just write let include over here is equal to zero.

62
00:03:38,920 --> 00:03:44,500
And the reason for that is we will not always be able to include the particular item or value that we

63
00:03:44,500 --> 00:03:45,280
are considering.

64
00:03:45,280 --> 00:03:55,210
And finally over here we would be saying depee at I j is the maximum between exclude and include.

65
00:03:56,290 --> 00:03:58,810
Now first what would be exclude.

66
00:03:58,810 --> 00:04:05,650
Now exclude is that we have to exclude or not take the current element that we are considering and then

67
00:04:05,650 --> 00:04:07,630
the previous value also does not change.

68
00:04:07,630 --> 00:04:07,960
Right.

69
00:04:07,960 --> 00:04:13,090
So that would be depee at I plus one and j itself.

70
00:04:13,090 --> 00:04:13,480
Okay.

71
00:04:13,480 --> 00:04:18,010
So we have J itself over here because the previous value does not change.

72
00:04:18,010 --> 00:04:21,730
And we have I plus one over here because we are moving the index by one.

73
00:04:21,730 --> 00:04:28,780
And again remember this means that you can start taking elements from index I plus one till the end

74
00:04:28,780 --> 00:04:29,560
of the Nums array.

75
00:04:29,560 --> 00:04:31,030
So that is what this means right.

76
00:04:31,030 --> 00:04:34,420
So we have not included the element at index I.

77
00:04:34,420 --> 00:04:38,920
And we can start including elements starting at index I plus one.

78
00:04:38,920 --> 00:04:40,570
So this is the exclude value.

79
00:04:40,570 --> 00:04:43,930
Now over here we have initialized include to be equal to zero.

80
00:04:43,930 --> 00:04:49,150
Now let's go ahead and check whether we can in fact include the element that we are considering.

81
00:04:49,150 --> 00:04:53,290
And for that either prev has to be equal to minus one.

82
00:04:53,290 --> 00:04:59,470
And again remember we have seen that we are incrementing the prev value by one to be able to fit it

83
00:04:59,470 --> 00:05:00,340
into the dp array.

84
00:05:00,340 --> 00:05:06,490
So whatever we get over here, as j has to be subtracted by one to get the actual prev value.

85
00:05:06,490 --> 00:05:11,440
And we are going to check whether j minus one is equal to minus one, which would mean that nothing

86
00:05:11,440 --> 00:05:16,900
has been added to the subsequence as of now, and therefore we will be able to include the element that

87
00:05:16,900 --> 00:05:18,820
we are considering into the subsequence.

88
00:05:18,820 --> 00:05:25,690
Now, if this is not the case, then we will have to check whether numb's at I is greater than numb's

89
00:05:25,690 --> 00:05:26,800
at prev okay.

90
00:05:26,800 --> 00:05:30,580
And again prev over here would be equal to j minus one.

91
00:05:30,580 --> 00:05:34,210
So we are checking whether numb's at I is greater than numb's at j minus one.

92
00:05:34,210 --> 00:05:37,210
Quickly repeating why do we have j minus one over here?

93
00:05:37,210 --> 00:05:44,650
That's because to get prev from the value of j, we have to subtract one from it because we added one

94
00:05:44,650 --> 00:05:46,000
to prev to get to j.

95
00:05:46,000 --> 00:05:46,390
Okay.

96
00:05:46,390 --> 00:05:48,340
So that's why we have j minus one over here.

97
00:05:48,340 --> 00:05:58,180
And if either of these is true then we can say that include is equal to one plus depee at I plus one.

98
00:05:58,630 --> 00:06:03,010
And then the new prev value which is the value at I or index I.

99
00:06:03,040 --> 00:06:09,100
But again because whenever we have a value for prev and when we want to include it into the DP table,

100
00:06:09,100 --> 00:06:11,230
we have to increment it by one.

101
00:06:11,230 --> 00:06:14,530
Okay, so that's DP at I plus one, I plus one.

102
00:06:14,620 --> 00:06:20,050
And over here we are doing one plus because we just included a particular element to the subsequence

103
00:06:20,050 --> 00:06:20,650
we are building.

104
00:06:20,650 --> 00:06:21,160
Okay.

105
00:06:21,160 --> 00:06:27,400
And then over here we have dp at I j is equal to the maximum between exclude and include.

106
00:06:27,400 --> 00:06:28,810
And that should do it.

107
00:06:28,810 --> 00:06:34,000
Now once we are out of this for loop we have to return DP at zero zero.

108
00:06:34,000 --> 00:06:38,110
Because we have discussed this is where we will be getting our answer again.

109
00:06:38,110 --> 00:06:40,840
I've quickly noticed there is an error over here, so I've missed this.

110
00:06:41,260 --> 00:06:45,940
All right, now let's go ahead and run this code and see if it's passing all the test cases.

111
00:06:46,810 --> 00:06:48,640
And you can see that it's working.

112
00:06:48,640 --> 00:06:50,260
It's passing all the test cases.

113
00:06:50,260 --> 00:06:55,840
So this is the tabulation approach using a 2D array for solving the Liz question.