The maximum length chain of pairs is a variation of the longest increasing subsequence problem. We have to find the pairs of numbers that have all the values in ascending order. The numbers in sets are always ordered in ascending order. So, for example, for those pairs: {{1, 2}, {5, 6}, {3, 5}} the longest length chain of pairs is 2, being formed by {{1, 2}, {3, 5}}. First, we sort the groups in order of their first element, and then we compare the first element from the second set to the second element from the first set, to see if they are ordered.
// Maximum Length Chain of Pairs
#include <stdio.h>
#include <stdlib.h>
struct pairOfNumbers
{
int firstNumber;
int secondNumber;
};
int maxLengthChainOfPairs(struct pairOfNumbers setOfPairs[], int sizeOfSet)
{
int maxLength = 0;
int *lengthOfArray = (int*)malloc(sizeof(int) * sizeOfSet);
for (int i = 0; i < sizeOfSet; i++)
{
lengthOfArray[i] = 1;
}
for(int i = 1; i < sizeOfSet; i++)
{
for(int j = 0; j < i; j++)
{
if(setOfPairs[i].firstNumber > setOfPairs[j].secondNumber && lengthOfArray[i] < lengthOfArray[j] + 1)
{
lengthOfArray[i] = lengthOfArray[j] + 1;
}
}
}
for(int i = 0; i < sizeOfSet; i++)
{
if(maxLength < lengthOfArray[i])
{
maxLength = lengthOfArray[i];
}
}
free(lengthOfArray);
return maxLength;
}
int main()
{
struct pairOfNumbers setOfPairs[] = {{10, 25}, {12, 27}, {30, 60}, {75, 90}};
int sizeOfSet = sizeof(setOfPairs)/sizeof(setOfPairs[0]);
printf("The Maximum Length Chain of Pairs is: %d", maxLengthChainOfPairs(setOfPairs, sizeOfSet));
return 0;
}
The Maximum Length Chain of Pairs is: 3
Comments