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.
public class MaxLengthChainOfPairs
{
public int maxChainLength(PairVal pair_arr[], int n)
{
int i, j, max = 0;
int MaxChainLen[] = new int[n];
for (i = 0; i < n; i++)
{
MaxChainLen[i] = 1;
}
for (i = 0; i < n; i++)
{
for (j = 0; j < i; j++)
{
if (pair_arr[i].a > pair_arr[j].b && MaxChainLen[i] < MaxChainLen[j] + 1)
MaxChainLen[i] = MaxChainLen[j] + 1;
}
}
for (i = 0; i < n; i++)
{
if (max < MaxChainLen[i])
max = MaxChainLen[i];
}
return max;
}
public static void main(String... arg)
{
PairVal pair_arr[] = new PairVal[4];
pair_arr[0] = new PairVal(5, 24);
pair_arr[1] = new PairVal(15, 25);
pair_arr[2] = new PairVal(27, 40);
pair_arr[3] = new PairVal(50, 60);
int n = 4;
MaxLengthChainOfPairs maxLengthChainOfPairs = new MaxLengthChainOfPairs();
System.out.println("the length of maximum size chain is "
+ maxLengthChainOfPairs.maxChainLength(pair_arr, n));
}
}
class PairVal
{
int a;
int b;
PairVal(int a, int b)
{
this.a = a;
this.b = b;
}
}
$ javac MaxLengthChainOfPairs.java $ java MaxLengthChainOfPairs the length of maximum size chain is 3
Related posts:
Java Program to Perform Partial Key Search in a K-D Tree
Creating Docker Images with Spring Boot
Write/Read cookies using HTTP and Read a file from the internet
Spring Cloud AWS – S3
Java Program to Implement Insertion Sort
Bootstrapping Hibernate 5 with Spring
Documenting a Spring REST API Using OpenAPI 3.0
Disable Spring Data Auto Configuration
Java Program to Implement Interpolation Search Algorithm
Java Byte Array to InputStream
What is Thread-Safety and How to Achieve it?
So sánh ArrayList và Vector trong Java
Spring Security Login Page with React
Comparing Dates in Java
Java Program to Evaluate an Expression using Stacks
Java Program to Compare Binary and Sequential Search
A Guide to Spring Cloud Netflix – Hystrix
Introduction to Eclipse Collections
Check If a File or Directory Exists in Java
Java Program to Implement Min Heap
Java – Write an InputStream to a File
Hướng dẫn Java Design Pattern – Memento
Lớp Properties trong java
Java Program to Find a Good Feedback Vertex Set
Finding the Differences Between Two Lists in Java
Spring Security Custom AuthenticationFailureHandler
Java Program to implement Bit Set
Custom Error Pages with Spring MVC
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
So sánh HashMap và HashSet trong Java
Vector trong Java
Hamcrest Collections Cookbook