資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在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;
// 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
更新於：2020年7月24日
138 次瀏覽
廣告