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