C++ में सबसे लंबा बिटोनिक अनुक्रम खोजें जैसे कि बढ़ते और घटते भाग दो अलग-अलग सरणियों से हों

अवधारणा

दो दी गई सरणियों के संबंध में, हमारा कार्य सबसे लंबा संभव बिटोनिक अनुक्रम निर्धारित करना है ताकि बढ़ता हुआ भाग पहली सरणी से हो और पहली सरणी का उपअनुक्रम होना चाहिए। इसी तरह, घटता हुआ भाग दूसरी सरणी से होना चाहिए और उसका उपअनुक्रम होना चाहिए।

इनपुट

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; // उपयोगिता बाइनरी खोज 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; } // उल्टे रूप में LIS खोजने वाला फ़ंक्शन void LIS(int arr[], int n){    // सीमा मामला जोड़ने के लिए उपयोग किया जाता है, जब सरणी n शून्य हो    // स्मार्ट पॉइंटर्स पर निर्भर करता है    vector<int> tailIndices1(n, 0); // 0 से इनिशियलाइज़    vector<int> prevIndices1(n, -1); // -1 से इनिशियलाइज़    int len1 = 1; // तो यह हमेशा खाली स्थान की ओर इशारा करेगा    for (int i = 1; i < n; i++) {       // नया सबसे छोटा मान दिखाता है       if (arr[i] < arr[tailIndices1[0]])          tailIndices1[0] = i;         // अब arr[i] सबसे बड़े उपअनुक्रम को बढ़ाना चाहता है       else if (arr[i] > arr[tailIndices1[len1 - 1]]) {          prevIndices1[i] = tailIndices1[len1 - 1];          tailIndices1[len1++] = i;       }       // यहां, arr[i] भविष्य के उपअनुक्रम का संभावित उम्मीदवार बनना चाहता है       // यह tailIndices में सीलिंग मान को प्रतिस्थापित करेगा       else {          int pos1 = GetCeilIndex(arr, tailIndices1, -1,          len1 - 1, arr[i]);          prevIndices1[i] = tailIndices1[pos1 - 1];          tailIndices1[pos1] = i;       }    }    // LIS (सबसे लंबा बढ़ता हुआ अनुक्रम) को वेक्टर में डालने के लिए उपयोग किया जाता है    for (int i = tailIndices1[len1 - 1]; i >= 0; i =       prevIndices1[i])       res1.push_back(arr[i]); } // सबसे लंबा बिटोनिक अनुक्रम खोजने वाला फ़ंक्शन void longestBitonic(int arr1[], int n1, int arr2[], int n2){    // सरणी 1 के LIS को उल्टे रूप में निर्धारित करें    LIS(arr1, n1);    // LIS को उल्टा करके पहली सरणी का LIS प्राप्त करें    reverse(res1.begin(), res1.end());    // सरणी2 को उल्टा करें और इसका LIS खोजें    reverse(arr2, arr2 + n2);    LIS(arr2, n2);    // अब परिणाम प्रिंट करें    for (int i = 0; i < res1.size(); i++)       cout << res1[i] << " "; } // ड्राइवर प्रोग्राम 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