# Maximum length of chain pairs

## In the given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c.

In the given pairs first element is always smaller than the second.

### Example

Input : [{12, 14}, {23, 29}, {18, 41}, {30,34}]
Output : 3

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

## Algorithm

Time complexity: O(n)

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

b. Here we use modified LIS,
1) Compare the first element of current and second element of chain created.
2) If no pairs in chain add the first pair.
3) If first element > second element of last in chain add element.
4) Else, replace.

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

## C++ Program

``````#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;
}``````

Scroll to Top