C++-এ দীর্ঘতম বাইটোনিক সাবসিকোয়েন্স-এর দৈর্ঘ্য বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি সংখ্যা অ্যারে দেওয়া থাকলে, এর দীর্ঘতম বাইটোনিক সাবসিকোয়েন্স (Longest Bitonic Subsequence) এর দৈর্ঘ্য খুঁজে বের করতে হবে। একটি সিকোয়েন্স বাইটোনিক হয় যখন সেটি প্রথমে কঠোরভাবে বৃদ্ধি পায় এবং তারপর কঠোরভাবে হ্রাস পায়। শুধু বৃদ্ধি বা শুধু হ্রাস পাওয়া সিকোয়েন্সও বাইটোনিক বলে বিবেচিত হয়।

উদাহরণ: nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] হলে আউটপুট 7।

সমাধানের পদ্ধতি

1. প্রতিটি ইন্ডেক্সে শেষ হওয়া দীর্ঘতম ক্রমবর্ধমান সাবসিকোয়েন্স (LIS) বের করুন → increasingSubSeq[]।
2. প্রতিটি ইন্ডেক্স থেকে শুরু হওয়া দীর্ঘতম ক্রমহ্রাসমান সাবসিকোয়েন্স (LDS) বের করুন → decreasingSubSeq[]।
3. প্রতিটি পজিশন i এর জন্য বাইটোনিক দৈর্ঘ্য = increasingSubSeq[i] + decreasingSubSeq[i] - 1।
4. সর্বোচ্চ মানটি রিটার্ন করুন।

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

#include <iostream>
#include <algorithm>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        increasingSubSeq[i] = 1;
    
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;
    
    int *decreasingSubSeq = new int[size];
    for (int i = 0; i < size; i++)
        decreasingSubSeq[i] = 1;
    
    for (int i = size - 2; i >= 0; i--)
        for (int j = size - 1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
    
    int maxLen = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > maxLen)
            maxLen = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
    
    return maxLen;
}

int main() {
    int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    int n = 16;
    cout << longBitonicSub(arr, n);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

আউটপুট: 7

জটিলতা

• সময়: O(n²)
• স্থান: O(n)