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 Implement Euler Circuit Problem
Java Program to Check whether Graph is Biconnected
How to Return 404 with Spring WebFlux
Hướng dẫn Java Design Pattern – Service Locator
Giới thiệu về Stream API trong Java 8
Phương thức tham chiếu trong Java 8 – Method References
Sắp xếp trong Java 8
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Spring Boot - Tomcat Deployment
Exploring the New Spring Cloud Gateway
Static Content in Spring WebFlux
Base64 encoding và decoding trong Java 8
Truyền giá trị và tham chiếu trong java
Serve Static Resources with Spring
Java Web Services – JAX-WS – SOAP
Filtering a Stream of Optionals in Java
Java Program to Test Using DFS Whether a Directed Graph is Strongly Connected or Not
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Java Program to Implement Ternary Tree
So sánh ArrayList và LinkedList trong Java
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Java Timer
The Difference Between Collection.stream().forEach() and Collection.forEach()
Spring Boot Tutorial – Bootstrap a Simple Application
Giới thiệu HATEOAS
LinkedHashSet trong java
Java Program to Implement Range Tree
Inject Parameters into JUnit Jupiter Unit Tests
Tính đa hình (Polymorphism) trong Java
Hướng dẫn Java Design Pattern – Memento
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Spring Autowiring of Generic Types