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

পদ্ধতি

প্রথম অ্যারে থেকে Longest Increasing Subsequence (LIS) এবং দ্বিতীয় অ্যারে থেকে Longest Decreasing Subsequence (LDS) খুঁজে বের করুন, তারপর দুটো একসাথে করুন। LIS বের করতে বাইনারি সার্চ 베이জড O(n log n) পদ্ধতি ব্যবহার করা হয়েছে।

উদাহরণ (C++ কোড)

// CPP: বিটোনিক সিকোয়েন্স খুঁজে বের করার জন্য
#include <bits/stdc++.h>
using namespace std;
vector res1;

// বাইনারি সার্চ ইউটিলিটি
int GetCeilIndex(int arr[], vector& 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) {
    vector tailIndices1(n, 0), prevIndices1(n, -1);
    int len1 = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[tailIndices1[0]]) tailIndices1[0] = i;
        else if (arr[i] > arr[tailIndices1[len1-1]]) {
            prevIndices1[i] = tailIndices1[len1-1];
            tailIndices1[len1++] = i;
        } else {
            int pos1 = GetCeilIndex(arr, tailIndices1, -1, len1-1, arr[i]);
            prevIndices1[i] = tailIndices1[pos1-1];
            tailIndices1[pos1] = i;
        }
    }
    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) {
    LIS(arr1, n1);
    reverse(res1.begin(), res1.end()); // প্রথম অ্যারের LIS
    reverse(arr2, arr2 + n2); // দ্বিতীয় অ্যারে রিভার্স করে এর LIS (যা LDS)
    LIS(arr2, n2);
    for (int i = 0; i < res1.size(); i++)
        cout << res1[i] << " ";
}

int main() {
    cout << "উদাহরণ: " << 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;
}

আউটপুট

উদাহরণ: 1 2 4 5 6 4 3 2