증가 부분과 감소 부분이 C++의 서로 다른 두 배열에서 나오도록 가장 긴 비트 시퀀스 찾기

컨셉

주어진 2개의 배열과 관련하여, 우리의 작업은 증가하는 부분이 첫 번째 배열에서 가져와야 하고 첫 번째 배열의 하위 시퀀스여야 하도록 가능한 가장 긴 비트 시퀀스를 결정하는 것입니다. 같은 방식으로 의 감소 부분은 두 번째 배열에서 가져와야 하며 그 하위 시퀀스여야 합니다.

입력

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