top of page
Caută
Poza scriitoruluioanaunciuleanu

Maximum Length Chain of Pairs in C++


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

56 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Comments


bottom of page