Java Program to Implement Maximum Length Chain of Pairs

This Java program Implements Maximum Length Chain Of Pairs.Given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs. Here is the source code of the Java Program to Implement Maximum Length Chain Of Pairs.The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
  1. public class MaxLengthChainOfPairs
  2. {
  3.     public int maxChainLength(PairVal pair_arr[], int n)
  4.     {
  5.         int i, j, max = 0;
  6.         int MaxChainLen[] = new int[n];
  7.         for (i = 0; i < n; i++)
  8.         {
  9.             MaxChainLen[i] = 1;
  10.         }
  11.         for (i = 0; i < n; i++)
  12.         {
  13.             for (j = 0; j < i; j++)
  14.             {
  15.                 if (pair_arr[i].a > pair_arr[j].b && MaxChainLen[i] < MaxChainLen[j] + 1)
  16.                     MaxChainLen[i] = MaxChainLen[j] + 1;
  17.             }
  18.         }
  19.         for (i = 0; i < n; i++)
  20.         {
  21.             if (max < MaxChainLen[i])
  22.                 max = MaxChainLen[i];
  23.         }
  24.         return max;
  25.     }
  26.  
  27.     public static void main(String... arg)
  28.     {
  29.         PairVal pair_arr[] = new PairVal[4];
  30.         pair_arr[0] = new PairVal(5, 24);
  31.         pair_arr[1] = new PairVal(15, 25);
  32.         pair_arr[2] = new PairVal(27, 40);
  33.         pair_arr[3] = new PairVal(50, 60);
  34.         int n = 4;
  35.         MaxLengthChainOfPairs maxLengthChainOfPairs = new MaxLengthChainOfPairs();
  36.         System.out.println("the length of maximum size chain is " 
  37.             + maxLengthChainOfPairs.maxChainLength(pair_arr, n));
  38.     }
  39. }
  40.  
  41. class PairVal
  42. {
  43.     int a;
  44.     int b;
  45.  
  46.     PairVal(int a, int b)
  47.     {
  48.         this.a = a;
  49.         this.b = b;
  50.     }
  51. }

$ javac MaxLengthChainOfPairs.java
$ java MaxLengthChainOfPairs
the length of maximum size chain is 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.