In the maximum length of chain pairs problem we have given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c. In the given pairs the first element is always smaller than the second.

## Example

**Input **

[{12, 14}, {23, 29}, {18, 41}, {30,34}]

**Output **

3

**Explanation**

Here, chain is {12, 14}, {23, 29}, {30, 34}

## Approach for Maximum Length of Chain Pairs

Here we use the modified way of the longest increasing subsequence algorithm. First, we need to sort the elements such a way that the first element is always in the increasing order. Now we apply the longest increasing subsequence to the current pair of the vector. Now, compare the first element of the current and second element of the chain created. If no pairs in chain add the first pair. If the first element > second element of last in chain add an element. Else, replace. Now for more understanding see the step by step execution of the logic-

arr[] = { {12, 14}, {23, 29}, {18, 41}, {30,34} };

First, we sort the array on the basis of the first element.

arr[] = { {12,14}, {18,41}, {23,29}, {30,34} }

Now add the elements to the chain and increase the counts of the length.

chain = { {12,14} }; //step 1;

chain = { {12,14}, {23,29}}; // step 2;

chain = { {12,14}, {23,29}, {30,34}}; //step 3;

## Algorithm

**a.** Sort the given pairs according, to the first element increasing order.

**b.** Here we use modified LIS,

- Compare the first element of the current and second element of the chain created.
- If no pairs in chain add the first pair.
- If the first element > second element of last in chain add an element.
- Else, replace.

**c.** Finally, return the length of the chain created.

## C++ Program for Maximum Length of Chain Pairs

#include <stdio.h> #include <stdlib.h> //pair structure struct pair { int a; int b; }; int MaxChainLen(struct pair array[], int n) { int i, j, maximum_len = 0; int *length_array = (int*) malloc ( sizeof( int ) * n ); //initilize length array for ( i = 0; i < n; i++ ) { length_array[i] = 1; } //algorithm for(i = 1; i < n; i++ ){ for(j = 0; j < i; j++ ) { if(array[i].a > array[j].b && length_array[i] < length_array[j] + 1) { length_array[i] = length_array[j] + 1; } } } for(i = 0; i < n; i++ ) { if(maximum_len < length_array[i] ) { maximum_len = length_array[i]; } } free( length_array ); return maximum_len; } /* Driver program to test above function */ int main() { struct pair input_array[] = {{12, 14}, {18, 41}, {23, 29}, {30, 34}}; int size = sizeof(input_array)/sizeof(input_array[0]); printf("length of longest chain is: %d",MaxChainLen(input_array,size)); return 0; }

length of longest chain is: 3

## Complexity Analysis for Maximum Length of Chain Pairs

**Time Complexity**

**O(nlogn) **where n is the number of given pairs. Here we rin two for loop which leads the time complexity to n^2.

### Space Complexity

**O(1)** because we just use a few variables as auxiliary space.