Tìm chuỗi bitonic dài nhất với phần tăng từ mảng 1 và phần giảm từ mảng 2 trong C++

Khái niệm

Cho hai mảng, tìm chuỗi bitonic dài nhất sao cho phần tăng phải từ mảng đầu tiên và là dãy con của mảng đó. Tương tự, phần giảm phải từ mảng thứ hai và là dãy con của nó.

Đầu vào

arr1[] = {2, 6, 3, 5, 4, 6}, arr2[] = {9, 7, 5, 8, 4, 3}

Đầu ra

2, 3, 4, 6, 9, 7, 5, 4, 3

Đầu vào

arr1[] = {3, 1, 2, 4, 5}, arr2[] = {6, 4, 3, 2}

Đầu ra

1, 2, 4, 5, 6, 4, 3, 2

Phương pháp

Ý tưởng: tìm dãy con tăng dần dài nhất (LIS) từ mảng 1 và dãy con giảm dần dài nhất (LDS) từ mảng 2, sau đó kết hợp cả hai.

Ví dụ

// CPP tìm chuỗi bitonic lớn nhất
#include <bits/stdc++.h>
using namespace std;
vector<int> res1;

// Tìm kiếm nhị phân utility
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;
}

// Hàm tìm LIS theo thứ tự ngược
void LIS(int arr[], int n){
    // Xử lý trường hợp n=0
    vector<int> tailIndices1(n, 0);
    vector<int> prevIndices1(n, -1);
    int len1 = 1;
    for (int i = 1; i < n; i++) {
        // Giá trị nhỏ mới
        if (arr[i] < arr[tailIndices1[0]])
            tailIndices1[0] = i;
        // arr[i] muốn mở rộng dãy con lớn nhất
        else if (arr[i] > arr[tailIndices1[len1 - 1]]) {
            prevIndices1[i] = tailIndices1[len1 - 1];
            tailIndices1[len1++] = i;
        }
        // arr[i] muốn là ứng viên cho dãy con tương lai
        else {
            int pos1 = GetCeilIndex(arr, tailIndices1, -1, len1 - 1, arr[i]);
            prevIndices1[i] = tailIndices1[pos1 - 1];
            tailIndices1[pos1] = i;
        }
    }
    // Đưa LIS vào vector
    for (int i = tailIndices1[len1 - 1]; i >= 0; i = prevIndices1[i])
        res1.push_back(arr[i]);
}

// Hàm tìm chuỗi bitonic dài nhất
void longestBitonic(int arr1[], int n1, int arr2[], int n2){
    // Tìm LIS của mảng 1 theo thứ tự ngược
    LIS(arr1, n1);
    // Đảo res để có LIS của mảng đầu tiên
    reverse(res1.begin(), res1.end());
    // Đảo mảng 2 và tìm LIS của nó
    reverse(arr2, arr2 + n2);
    LIS(arr2, n2);
    // In kết quả
    for (int i = 0; i < res1.size(); i++)
        cout << res1[i] << " ";
}

// Chương trình chính
int main(){
    cout<<"Ví dụ:"<< 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;
}

Đầu ra

Ví dụ: 1 2 4 5 6 4 3 2