Maximum Length Chain of Pairs | DSA in C++ - Software Development PDF Download

Introduction

The Maximum Length Chain of Pairs problem is a common dynamic programming problem in computer science. It involves finding the longest chain of pairs in an array where each pair (a, b) follows a specific condition. In this article, we will explore this problem, discuss the approach to solve it, provide sample code with explanations, and conclude with a few sample problems and their solutions.

Problem Statement

Given an array of pairs, each pair (a, b) represents two integers, where a < b. The task is to find the length of the maximum chain that can be formed by connecting pairs (a, b) such that the second element of the pair is greater than the first element of the next pair.

Example:

Input: [(5, 24), (39, 60), (15, 28), (27, 40), (50, 60)]

Output: 3

Explanation: The maximum length chain is (5, 24) -> (27, 40) -> (50, 60).

Approach

To solve this problem, we can use dynamic programming. The idea is to sort the given pairs based on the first element. Then, we can apply the longest increasing subsequence (LIS) algorithm to find the maximum chain length.

The steps to solve the problem are as follows:

• Sort the pairs based on the first element in ascending order.
• Initialize an array, dp[], of the same size as the number of pairs, filled with 1.
• Iterate through each pair and calculate dp[i] as the maximum of dp[j] + 1, where j < i and pair[j].second < pair[i].first.
• Return the maximum value in the dp[] array.

Implementation in C++

Here is the C++ code that implements the above approach:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Pair {

    int first, second;

};

int maxChainLength(vector<Pair>& pairs) {

    sort(pairs.begin(), pairs.end(), [](const Pair& a, const Pair& b) {

        return a.first < b.first;

    });

    int n = pairs.size();

    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (pairs[j].second < pairs[i].first) {

                dp[i] = max(dp[i], dp[j] + 1);

            }

        }

    }

    return *max_element(dp.begin(), dp.end());

}

int main() {

    vector<Pair> pairs = { {5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 60} };

    int length = maxChainLength(pairs);

    cout << "Maximum Length Chain of Pairs: " << length << endl;

    return 0;

}

Sample Code and Output

In the above code, we create a structure 'Pair' to represent a pair of integers. We sort the pairs based on the first element and then use the dynamic programming approach to find the maximum chain length. Finally, we print the result.

Output:

Maximum Length Chain of Pairs: 3

Sample Problems and Solutions

Problem 1: Input: [(1, 2), (3, 4), (5, 6)]

Output: 3

The maximum length chain is (1, 2) -> (3, 4) -> (5, 6).

Problem 2: Input: [(1, 2), (2, 3), (3, 4)]

Output: 1

In this case, there is no chain of pairs where the second element is greater than the first element of the next pair. Hence, the maximum length chain is 1.

Conclusion

In this article, we discussed the Maximum Length Chain of Pairs problem and provided an easy-to-understand explanation of the approach to solve it. We also provided a C++ implementation with sample code and output. Finally, we included a few sample problems and their solutions to further clarify the concepts. By understanding this problem and its solution, you will gain a better understanding of dynamic programming and its application in solving real-world problems.