Chuỗi cặp số dài nhất trong C++

Cho một chuỗi các cặp số. Mỗi cặp có hai số nguyên, số đầu luôn nhỏ hơn số sau. Quy tắc chuỗi: cặp (x, y) có thể thêm sau cặp (p, q) chỉ nếu q < x.

Giải pháp: sắp xếp các cặp theo thứ tự tăng dần của phần tử đầu. Sau đó so sánh phần tử thứ hai của cặp này với phần tử đầu của cặp tiếp theo.

Đầu vào

Chuỗi cặp số: {(5, 24), (15, 25), (27, 40), (50, 60)}

Đầu ra

Độ dài chuỗi lớn nhất: 3.

Thuật toán

maxChainLength(arr, n) mỗi phần tử chứa a và b
Đầu vào: Mảng cặp, số lượng phần tử.
Đầu ra: Độ dài tối đa.
Bắt đầu
    định nghĩa mảng maxChainLen kích thước n, điền 1
    max := 0
    cho i := 1 đến n, làm
        cho j := 0 đến i-1, làm
            nếu arr[i].a > arr[j].b và maxChainLen[i] < maxChainLen[j] + 1
                maxChainLen[i] := maxChainLen[j] + 1
            kết thúc nếu
        kết thúc
    kết thúc
    max := giá trị lớn nhất trong mảng maxChainLen
    trả về max
Kết thúc

Ví dụ mã C++

#include<iostream>
#include<algorithm>
using namespace std;

struct numPair{
    int a;
    int b;
};

int maxChainLength(numPair arr[], int n){
    int max = 0;
    int *maxChainLen = new int[n];
    for (int i = 0; i < n; i++ )
        maxChainLen[i] = 1;
    for (int i = 1; i < n; i++ )
        for (int j = 0; j < i; j++ )
            if ( arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)
                maxChainLen[i] = maxChainLen[j] + 1;
    for (int i = 0; i < n; i++ )
        if ( max < maxChainLen[i] )
            max = maxChainLen[i];
    delete[] maxChainLen;
    return max;
}

int main(){
    struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
    int n = 4;
    cout << "Độ dài chuỗi lớn nhất là " << maxChainLength(arr, n);
}

Kết quả đầu ra

Độ dài chuỗi lớn nhất là 3