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 SimpeBindings API
Annotation trong Java 8
Java Program to Implement Dijkstra’s Algorithm using Queue
Jackson – Decide What Fields Get Serialized/Deserialized
Count Occurrences of a Char in a String
Guide to CountDownLatch in Java
Java Program to implement Associate Array
Java Program to Implement Euler Circuit Problem
Java – InputStream to Reader
Hướng dẫn Java Design Pattern – Strategy
Chương trình Java đầu tiên
Spring Security Registration – Resend Verification Email
Servlet 3 Async Support with Spring MVC and Spring Security
Java Program to Encode a Message Using Playfair Cipher
Java Program to Find a Good Feedback Edge Set in a Graph
A Guide to TreeMap in Java
REST Web service: Basic Authentication trong Jersey 2.x
Java NIO2 Path API
Java Program to Implement Self Balancing Binary Search Tree
Getting the Size of an Iterable in Java
Java – String to Reader
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Java Program to Implement Hash Tables Chaining with List Heads
How to Iterate Over a Stream With Indices
Jackson – Unmarshall to Collection/Array
Weak References in Java
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Converting a Stack Trace to a String in Java
Java Program to Perform Left Rotation on a Binary Search Tree
String Operations with Java Streams
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
New Stream Collectors in Java 9