Chuỗi cặp có chiều dài tối đa

Có một chuỗi các cặp được đưa ra. Trong mỗi cặp, có hai số nguyên và số nguyên đầu tiên luôn nhỏ hơn và số thứ hai lớn hơn, quy tắc tương tự cũng có thể được áp dụng cho việc xây dựng chuỗi. Một cặp (x, y) có thể được thêm vào sau một cặp (p, q), chỉ khi q

Để giải quyết vấn đề này, đầu tiên, chúng ta phải sắp xếp các cặp đã cho theo thứ tự tăng dần của phần tử đầu tiên. Sau đó, chúng tôi sẽ so sánh phần tử thứ hai của một cặp với phần tử đầu tiên của cặp tiếp theo.

Đầu vào và Đầu ra

Input:
A chain of number pairs. {(5, 24), (15, 25), (27, 40), (50, 60)}
Output:
Largest length of the chain as given criteria. Here the length is 3.

Thuật toán

maxChainLength(arr, n)

Mỗi phần tử của chuỗi sẽ chứa hai phần tử a và b

Đầu vào - Mảng các cặp, số lượng các mục trong mảng.

Đầu ra - Chiều dài tối đa.

Begin
   define maxChainLen array of size n, and fill with 1
   max := 0

   for i := 1 to n, do
      for j := 0 to i-1, do
         if arr[i].a > arr[j].b and maxChainLen[i] < maxChainLen[j] + 1
            maxChainLen[i] := maxChainLen[j] + 1
      done
   done

   max := maximum length in maxChainLen array
   return max
End

Ví dụ

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

struct numPair {    //define pair as structure
   int a;
   int b;
};

int maxChainLength(numPair arr[], int n) {
   int max = 0;
   int *maxChainLen = new int[n];    //create array of size n

   for (int i = 0; i < n; i++ )    //Initialize Max Chain length values for all indexes
      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;

   // maxChainLen[i] now holds the max chain length ending with pair i

   for (int i = 0; i < n; i++ )
      if ( max < maxChainLen[i] )
         max = maxChainLen[i];    //find maximum among all chain length values
   delete[] maxChainLen;    //deallocate memory
   return max;
}

int main() {
   struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
   int n = 4;
   cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}

Đầu ra

Length of maximum size chain is 3