Chuỗi cặp số dài nhất (Maximum Length Chain of Pairs)

Cho một chuỗi các cặp số (a, b) với a < b. Một cặp (x, y) có thể nối sau cặp (p, q) nếu q < x. Tìm độ dài chuỗi dài nhất thỏa mãn điều kiện.

Đầu vào / Đầu ra

Input: {(5, 24), (15, 25), (27, 40), (50, 60)}
Output: 3  (chuỗi: (5,24) -> (27,40) -> (50,60))

Thuật toán (Dynamic Programming)

1. Sắp xếp các cặp theo phần tử đầu tăng dần.
2. Khởi tạo mảng maxChainLen[n] toàn giá trị 1.
3. Với mỗi cặp i từ 1 đến n-1, duyệt j từ 0 đến i-1:
   • Nếu arr[i].a > arr[j].b và maxChainLen[i] < maxChainLen[j] + 1 thì cập nhật maxChainLen[i] = maxChainLen[j] + 1.
4. Kết quả là giá trị lớn nhất trong mảng maxChainLen.

Code 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() {
  numPair arr[] = {{5, 24}, {15, 25}, {27, 40}, {50, 60}};
  int n = 4;
  cout << "Length of maximum size chain is " << maxChainLength(arr, n);
  return 0;
}

Kết quả

Length of maximum size chain is 3