ধারণা
প্রদত্ত দুটি অ্যারের সাপেক্ষে, আমাদের কাজ হল দীর্ঘতম সম্ভাব্য বিটোনিক ক্রম নির্ধারণ করা যাতে ক্রমবর্ধমান অংশটি প্রথম অ্যারে থেকে হতে হবে এবং প্রথম অ্যারের পরবর্তী অংশ হওয়া উচিত। একইভাবে, এর হ্রাস করা অংশ অবশ্যই দ্বিতীয় অ্যারে থেকে হতে হবে এবং এটির একটি পরবর্তী অংশ হওয়া উচিত।
ইনপুট
arr1[] = {2, 6, 3, 5, 4, 6},
arr2[] = {9, 7, 5, 8, 4, 3} আউটপুট
2, 3, 4, 6, 9, 7, 5, 4, 3
ইনপুট
arr1[] = {3, 1, 2, 4, 5},
arr2[] = {6, 4, 3, 2} আউটপুট
1, 2, 4, 5, 6, 4, 3, 2
পদ্ধতি
সুতরাং ধারণাটি হল অ্যারে 1 থেকে দীর্ঘতম ক্রমবর্ধমান ক্রম এবং অ্যারে2 থেকে দীর্ঘতম ক্রমবর্ধমান ক্রম প্রয়োগ করা এবং তারপরে আমাদের ফলাফল পেতে উভয়কে একত্রিত করা৷
উদাহরণ
// 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;
} আউটপুট
Example: 1 2 4 5 6 4 3 2
