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:
Spring Boot - Web Socket
Java Program to Solve the Fractional Knapsack Problem
Spring Boot - Building RESTful Web Services
Phương thức forEach() trong java 8
Introduction to Spring Data JPA
Jackson – JsonMappingException (No serializer found for class)
Guide to java.util.concurrent.BlockingQueue
Java Program to Use rand and srand Functions
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Java Program to Implement LinkedBlockingDeque API
Java Program to Implement Efficient O(log n) Fibonacci generator
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Spring Security Custom AuthenticationFailureHandler
Java Program to Implement Karatsuba Multiplication Algorithm
Rate Limiting in Spring Cloud Netflix Zuul
Spring Security – security none, filters none, access permitAll
Checked and Unchecked Exceptions in Java
Java Program to Perform Search in a BST
ArrayList trong java
Spring REST with a Zuul Proxy
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Java Program to Implement HashSet API
Multipart Upload with HttpClient 4
New Features in Java 14
Jackson – Bidirectional Relationships
Prevent Cross-Site Scripting (XSS) in a Spring Application
Removing all Nulls from a List in Java
Java Program to Perform Cryptography Using Transposition Technique
Java Program to Find Nearest Neighbor for Static Data Set
File Upload with Spring MVC
Setting the Java Version in Maven