แนวคิด
เมื่อได้รับอาร์เรย์สองอาร์เรย์ งานของเราคือหาลำดับ Bitonic ที่ยาวที่สุดที่เป็นไปได้ เพื่อให้ increasing part ต้องมาจากอาร์เรย์แรกและต้องเป็น subsequence ของอาร์เรย์แรก ในทางเดียวกัน decreasing part ต้องมาจากอาร์เรย์ที่สองและต้องเป็น subsequence ของมัน
อินพุต
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
วิธีการ
แนวคิดคือใช้ longest increasing sequence จาก array1 และ longest decreasing sequence จาก array2 แล้วนำมารวมกันเพื่อได้ผลลัพธ์
ตัวอย่างโค้ด
// CPP to find largest bitonic sequence such that #include <bits/stdc++.h> using namespace std; vector<int> res1; // 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; } // ฟังก์ชันแสดงการหา LIS ในรูปแบบ reverse void LIS(int arr[], int n){ // ใช้เพิ่ม boundary case เมื่อ array n เป็นศูนย์ // ขึ้นอยู่กับ smart pointers vector<int> tailIndices1(n, 0); // เริ่มต้นด้วย 0 vector<int> prevIndices1(n, -1); // เริ่มต้นด้วย -1 int len1 = 1; // ดังนั้นจะชี้ไปที่ empty location เสมอ for (int i = 1; i < n; i++) { // แสดงค่าใหม่ที่เล็กที่สุด if (arr[i] < arr[tailIndices1[0]]) tailIndices1[0] = i; // ตอนนี้ arr[i] ต้องการขยาย largest subsequence else if (arr[i] > arr[tailIndices1[len1 - 1]]) { prevIndices1[i] = tailIndices1[len1 - 1]; tailIndices1[len1++] = i; } // ที่นี่ arr[i] ต้องการเป็น potential candidate ของ // future subsequence // มันจะแทนที่ ceil value ใน tailIndices else { int pos1 = GetCeilIndex(arr, tailIndices1, -1, len1 - 1, arr[i]); prevIndices1[i] = tailIndices1[pos1 - 1]; tailIndices1[pos1] = i; } } // ใช้ใส่ LIS(Longest Increasing Sequence) ลง vector for (int i = tailIndices1[len1 - 1]; i >= 0; i = prevIndices1[i]) res1.push_back(arr[i]); } // ฟังก์ชันสำหรับหา longest bitonic seq void longestBitonic(int arr1[], int n1, int arr2[], int n2){ // หา LIS ของ array 1 ในรูปแบบ reverse LIS(arr1, n1); // ใช้ reverse res เพื่อได้ LIS ของอาร์เรย์แรก reverse(res1.begin(), res1.end()); // ใช้ reverse array2 และหา LIS ของมัน reverse(arr2, arr2 + n2); LIS(arr2, n2); // ตอนนี้พิมพ์ผลลัพธ์ for (int i = 0; i < res1.size(); i++) cout << res1[i] << " "; } // driver program 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
