Chuỗi các cặp có độ dài tối đa trong C ++

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ố nguyên 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 - Một chuỗi các cặp số. {(5, 24), (15, 25), (27, 40), (50, 60)}

Đầu ra - Chiều dài lớn nhất của chuỗi theo tiêu chí đã cho. Ở đây độ dài là 3.

Thuật toán

maxChainLength(arr, n)
each element of chain will contain two elements a and b
Input: The array of pairs, number of items in the array.
Output: Maximum length.
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