Khái niệm
Đối với hai mảng đã cho, nhiệm vụ của chúng ta là xác định chuỗi bitonic dài nhất có thể để phần tăng dần phải từ mảng đầu tiên và phải là dãy con của mảng đầu tiên. Theo cách tương tự, giảm một phần của phải từ mảng thứ hai và phải là một dãy con của nó.
Đầu vào
arr1[] = {2, 6, 3, 5, 4, 6},
arr2[] = {9, 7, 5, 8, 4, 3} Đầu ra
2, 3, 4, 6, 9, 7, 5, 4, 3
Đầu vào
arr1[] = {3, 1, 2, 4, 5},
arr2[] = {6, 4, 3, 2} Đầu ra
1, 2, 4, 5, 6, 4, 3, 2
Phương pháp
Vì vậy, khái niệm là triển khai chuỗi tăng dài nhất từ mảng 1 và chuỗi giảm dài nhất từ mảng 2 và sau đó kết hợp cả hai để thu được kết quả của chúng tôi.
Ví dụ
// CPP to find largest bitonic sequence such that
#include <bits/stdc++.h>
using namespace std;
vector<int> res1;
// Shows utility Binary search
int GetCeilIndex(int arr[], vector<int>& T1, int l1,
int r1, int key1){
while (r1 - l1 > 1) {
int m1 = l1 + (r1 - l1) / 2;
if (arr[T1[m1]] >= key1)
r1 = m1;
else
l1 = m1;
}
return r1;
}
// Shows function to find LIS in reverse form
void LIS(int arr[], int n){
// Used to add boundary case, when array n is zero
// Depend on smart pointers
vector<int> tailIndices1(n, 0); // Initialized with 0
vector<int> prevIndices1(n, -1); // initialized with -1
int len1 = 1; // So it will always point to empty location
for (int i = 1; i < n; i++) {
// Shows new smallest value
if (arr[i] < arr[tailIndices1[0]])
tailIndices1[0] = i;
// Now arr[i] wants to extend largest subsequence
else if (arr[i] > arr[tailIndices1[len1 - 1]]) {
prevIndices1[i] = tailIndices1[len1 - 1];
tailIndices1[len1++] = i;
}
// Here, arr[i] wants to be a potential candidate of
// future subsequence
// It will replace ceil value in tailIndices
else {
int pos1 = GetCeilIndex(arr, tailIndices1, -1,
len1 - 1, arr[i]);
prevIndices1[i] = tailIndices1[pos1 - 1];
tailIndices1[pos1] = i;
}
}
// Used to put LIS(Longest Increasing Sequence) into vector
for (int i = tailIndices1[len1 - 1]; i >= 0; i =
prevIndices1[i])
res1.push_back(arr[i]);
}
// Shows function for finding longest bitonic seq
void longestBitonic(int arr1[], int n1, int arr2[], int n2){
// Determine LIS of array 1 in reverse form
LIS(arr1, n1);
// Used to reverse res to get LIS of first array
reverse(res1.begin(), res1.end());
// Used to reverse array2 and find its LIS
reverse(arr2, arr2 + n2);
LIS(arr2, n2);
// Now print result
for (int i = 0; i < res1.size(); i++)
cout << res1[i] << " ";
}
// driver preogram
int main(){
cout<<"Example:"<< endl;
int arr1[] = {3, 1, 2, 4, 5};
int arr2[] = {6, 4, 3, 2};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
longestBitonic(arr1, n1, arr2, n2);
return 0;
} Đầu ra
Example: 1 2 4 5 6 4 3 2