सबसे लंबा बिटोनिक अनुक्रम खोजें जैसे कि बढ़ते और घटते हिस्से 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

विधि

तो अवधारणा यह है कि array1 से सबसे लंबे समय तक बढ़ते अनुक्रम को लागू किया जाए और array2 से सबसे लंबे समय तक घटते क्रम को लागू किया जाए और फिर दोनों को मिलाकर हमारा परिणाम प्राप्त किया जाए।

उदाहरण

// 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