Solve the Maximum Length of Pair Chain problem using dynamic programming.?

The Maximum Length of Pair Chain problem is as follows:

You are given n pairs of numbers where each pair consists of two numbers. You are required to find the maximum length of pair chain. A pair (c, d) can follow another pair (a, b) if and only if b < c. So, you have to find the longest possible chain of these pairs such that pairwise second number of each pair is less than the first number of the next pair.

To solve this problem using dynamic programming, we need to define a subproblem and find the recurrence relation.

Subproblem: Given a pair (c, d), what is the length of the longest chain ending at (c, d)?

Let dp[i] represent the length of the longest chain ending at the i-th pair with 0 <= i < n.

We can sort the pairs based on their first element in increasing order, i.e., pairs[i][0] < pairs[j][0] if i < j. This will allow us to only look at pairs that could come before a given pair in the chain.

Now, we can use bottom-up dynamic programming to solve the problem. We start by initializing dp[i] to 1 for all i.

For i in range [1, n), we look for all pairs j where j < i and pairs[j][1] < pairs[i][0]. Then we update dp[i] to max(dp[i], dp[j] + 1). This is because we can add the current pair after the longest chain ending at j to make a longer chain ending at i.

Finally, the answer is the maximum value in dp array.

Here is the Java code that implements the above dynamic programming approach:

public int findLongestChain(int[][] pairs) {
    int n = pairs.length;
    Arrays.sort(pairs, (a, b) -> a[0] - b[0]); // sort based on first element
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    int maxLen = 0;
    for (int len : dp) {
        maxLen = Math.max(maxLen, len);
    }
    return maxLen;
}

Let’s run an example to see how it works:

Input pairs: [[1,2], [2,3], [3,4]]
Output: 2

Explanation: The longest chain is [1,2] -> [3,4] and its length is 2.