查找最长的双音序列，使得递增和递减的部分来自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;
//显示实用程序二进制搜索
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); // 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++) {
//显示新的最小值
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;
}
//的潜在候选者
//未来子序列
//ceil值
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);
//用于反转res以获取第一个数组的LIS-
reverse(res1.begin(), res1.end());
//用于反转array2并找到其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