Welcome back.
Let's now discuss how we can solve this question.
And we will be taking the tabulation or bottom up approach for solving this question, because we are
already familiar with the list type.
Okay.
So previously we have discussed the recursive approach, the memoization approach, as well as the tabulation
approach for solving the list question.
So let's go ahead and take a look at how we can use what we have learned over there to solve this question.
And for this let's take an example.
Let's say this is the array which is given to us.
So it has three elements.
And each element is such that the first element in that particular array has the lower value.
For example over here notice four is less than five, two is less than nine, and one is less than two.
Now the first step is to sort this.
And we have discussed in the previous video why we need to do this.
So once we have sorted these elements this is how the array would look like.
Notice we have one over here, two over here and four over here.
Now once we are done sorting the array which is given to us, we will have a DP array.
And initially we will fill each cell with the value one.
So over here we have three elements.
So that's why in the DP array we have three cells and each value is filled with one.
Now notice that this is the same thing that we did for the tabulation approach, the 1D tabulation approach
when we discussed the list question.
So what we will do is we'll have a nested for loop.
So one variable would be I and I will go from the value one up to the last index okay.
So in this case that's one up to two.
And for each value of I j will take the values zero to I minus one.
This is exactly the same thing that we did for the list question.
And at every point or for every combination of I and J, we will check two things.
Now let's take an example.
Let's say I is over here and J is over here okay.
So at this point we will check whether this value over here is less than this value, because that's
the condition mentioned in the question for forming a chain of pairs okay.
And over here we see that that's not the case.
But let's say if it was the case then we would also check whether depee at J plus one is greater than
depee at I.
Okay.
Remember this is the same thing that we did in the list question as well.
So let's go ahead and see how the algorithm solves this question.
So initially I is equal to one and j takes the value zero.
And we are comparing these two values.
We see that this value over here is not less than this value okay.
And because of that reason we will not be able to form a chain of pairs using these two elements.
Therefore we move forward.
So I takes the value two and j will take the values zero as well as one.
So initially j takes the value zero.
Now we will check whether this value over here is less than this value which is the case okay two is
less than four.
So that means that we can form a chain of pairs where this is the first element.
And this over here is the second element.
Now we also need to check whether depee at j plus one is greater than depee at I.
Okay.
So at this point depee at j is this value over here because j is pointing at index zero.
So we have zero over here, one over here and two over here.
And we have zero over here, one over here and two over here.
So depee at J is this value.
And one plus one which is two is in fact greater than depee at I which is this value which is just one.
So two is greater than one.
Therefore we are going to modify the value of dp at I, and we will set it to dp at j plus one.
Okay.
And then we move forward.
So j over here took the value zero.
Now when we move forward j will take the value one.
And at this point again we're going to check whether this value is less than this value.
And we see that that's not the case okay.
And therefore we can't make a chain of pairs using these two elements.
And again because we have reached the last value for I we are done.
Okay.
Now we have this updated DP array over here.
And we will just find the maximum value among all these elements.
And that is our answer.
So in this case we are getting a length of two which is the chain of pairs where we have one comma two
and then we have four comma five okay.
And the length of this.
Chain of pairs is equal to two.
So this is the bottom up or tabulation approach which we can use to solve the max pair chain problem.
In the next video, let's discuss the complexity analysis of the approach that we have discussed over
here.