1
00:00:00,110 --> 00:00:07,010
Let's now get into the code and implement the tabulation approach using a 1D array for solving the Liz

2
00:00:07,010 --> 00:00:07,610
question.

3
00:00:07,610 --> 00:00:12,260
So let's say n is the length of the given numb's array.

4
00:00:12,260 --> 00:00:14,240
And we would need a DP array.

5
00:00:14,240 --> 00:00:17,780
Let's just call it dp itself which has the same size okay.

6
00:00:17,780 --> 00:00:21,860
So we can say let DP is equal to array and the length is n itself.

7
00:00:21,860 --> 00:00:27,260
And we will fill, as we have discussed in the previous video, every cell in this array with the value

8
00:00:27,260 --> 00:00:28,280
one okay.

9
00:00:28,280 --> 00:00:32,030
And initially let's say max is equal to one.

10
00:00:32,030 --> 00:00:38,150
So this will be the variable which we will use to keep track of the maximum Liz found so far.

11
00:00:38,150 --> 00:00:41,570
And ultimately we will be just returning Max.

12
00:00:41,810 --> 00:00:44,810
So this is the skeleton of the approach that we will be taking.

13
00:00:44,810 --> 00:00:51,350
Now again over here, if we see that n is equal to zero then we can just return zero okay.

14
00:00:51,350 --> 00:00:54,290
So that's just to handle an edge case.

15
00:00:54,290 --> 00:01:01,880
Now once we have the DP array let's now iterate through the cells in the DP array starting at index

16
00:01:01,880 --> 00:01:02,990
one okay.

17
00:01:02,990 --> 00:01:11,720
So I can say for I is equal to one I less than n because the last valid index is n minus one I plus

18
00:01:11,720 --> 00:01:12,080
plus.

19
00:01:12,080 --> 00:01:17,810
And for each value of I, j will take the values from zero up to I minus one.

20
00:01:17,810 --> 00:01:24,380
So I can say for j is equal to zero j less than I j plus plus.

21
00:01:24,380 --> 00:01:24,920
All right.

22
00:01:24,920 --> 00:01:28,700
Now what we will do is we will take pairs of I and J.

23
00:01:28,700 --> 00:01:34,850
And we will try to see whether numb's at I is greater than numb's at J.

24
00:01:35,420 --> 00:01:45,410
And if we see that that is the case, then we will check whether depee at J plus one okay is greater

25
00:01:45,410 --> 00:01:46,850
than depee at I.

26
00:01:48,030 --> 00:01:54,570
Because if that is the case, then we would have identified a longer subsequence ending with the value

27
00:01:54,570 --> 00:01:55,560
at index I.

28
00:01:55,560 --> 00:02:00,960
And therefore over here we would say depee at I, which initially had the value one, because that's

29
00:02:00,960 --> 00:02:04,800
what we filled over here in the DP table at every cell.

30
00:02:04,800 --> 00:02:08,610
So we would change that value to depee at j plus one.

31
00:02:09,450 --> 00:02:09,900
Okay.

32
00:02:09,900 --> 00:02:15,990
So again in this case the subsequence that we are building would be ending with the value at index I.

33
00:02:16,350 --> 00:02:22,860
And after that, once we are out of this for loop, remember we have to check whether the value that

34
00:02:22,860 --> 00:02:27,540
we got for DP at I is greater than max, because ultimately we are returning max over here.

35
00:02:27,540 --> 00:02:28,590
So let's check that.

36
00:02:28,590 --> 00:02:36,090
So if dp at I is greater than max, then we would just say max is equal to dp at I.

37
00:02:36,750 --> 00:02:37,170
All right.

38
00:02:37,170 --> 00:02:42,840
So this helps us because otherwise we would have to pass through the DP array one more time to identify

39
00:02:42,840 --> 00:02:44,520
the largest value in the DP array.

40
00:02:44,520 --> 00:02:45,480
And that's it.

41
00:02:45,480 --> 00:02:49,620
Now let's go ahead and run this code and see if it's passing all the test cases.

42
00:02:50,820 --> 00:02:52,590
And you can see that it's working.

43
00:02:52,590 --> 00:02:54,270
It's passing all the test cases.