আকার ৩ এর বাড়মান সাবসিকোয়েন্সের সর্বোচ্চ গুণফল (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক ধনাত্মক পূর্ণসংখ্যা সহ একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল আকার ৩ এর বাড়মান সাবসিকোয়েন্সের সর্বোচ্চ গুণফল খুঁজে বের করার প্রোগ্রাম তৈরি করা।

এখানে, আমাদের অ্যারেতে ৩টি উপাদান বের করতে হবে যেন সেগুলো একটি বাড়মান সাবসিকোয়েন্স তৈরি করে এবং অ্যারে ইনডেক্সও বাড়ছে অর্থাৎ:

arr[i]*arr[j]*arr[k] সর্বোচ্চ, arr[i] < arr[j] < arr[k] এবং i < j < k

arr = {5, 9, 2, 11, 4, 7}

495

শর্ত পূরণকারী আকার ৩ এর সকল সাবঅ্যারে:
(5, 9, 11), গুণফল = 5*9*11 = 495
(2, 4, 7), গুণফল = 2*4*7 = 56
সর্বোচ্চ = 495

একটি সহজ পদ্ধতি হল অ্যারে লুপ চালিয়ে শর্ত পূরণকারী আকার ৩ এর সকল সাবঅ্যারে বের করা। উপাদানগুলোর গুণফল বের করে সব গুণফলের মধ্যে সর্বোচ্চটি ফেরত দেওয়া।

আরম্ভিকরণ:

maxProd = -1000

ধাপ ১: i → 0 থেকে n-3 পর্যন্ত লুপ।

ধাপ ১.১: j → i থেকে n-2 পর্যন্ত লুপ।

ধাপ ১.১.১: if(arr[i] < arr[j]) → k → j থেকে n-1 পর্যন্ত লুপ।

ধাপ ১.১.১.১: if(arr[j] < arr[k]) → prod = arr[i]*arr[j]*arr[k] বের করুন।

ধাপ ১.১.১.২: if(maxProd < prod) → maxProd = prod।

ধাপ ২: maxProd ফেরত দিন।

#include 
using namespace std;

int calcMaxProd(int arr[], int n) {
    int maxProd = -1000;
    int prod;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            if (arr[i] < arr[j]) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[j] < arr[k]) {
                        prod = arr[i] * arr[j] * arr[k];
                        if (maxProd < prod)
                            maxProd = prod;
                    }
                }
            }
    return maxProd;
}

int main() {
    int arr[] = { 5, 9, 2, 11, 4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum product of an increasing subsequence of size 3 is " << calcMaxProd(arr, n);
    return 0;
}

The maximum product of an increasing subsequence of size 3 is 495

এই সমাধান সহজ হলেও ৩টি নেস্টেড লুপ ব্যবহার করে যা টাইম কমপ্লেক্সিটি O(n³) করে দেয়। তাই আসুন একটি দক্ষ সমাধান দেখি।

এই সমাধানে, আমরা অ্যারেতে ইনডেক্স ১ থেকে n-2 পর্যন্ত উপাদানগুলো নিব। এবং সেটিকে আমাদের ৩ উপাদানের সাবঅ্যারের মাঝপথের উপাদান হিসেবে বিবেচনা করব। এবং বাকি দুটি উপাদান অ্যারেতে থেকে বের করব।

ইনডেক্স i-র চেয়ে কম ইনডেক্সে arr[i]-এর চেয়ে ছোট উপাদান।
ইনডেক্স i-র চেয়ে বড় ইনডেক্সে arr[i]-এর চেয়ে বড় উপাদান।

সবচেয়ে ছোট উপাদান সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি ব্যবহার করে বের করা হয় এবং সবচেয়ে বড় উপাদান ডান পাশ থেকে বামে ট্রভার্স করে বের করা হয়।

দুটি মান পাওয়ার পর, আমরা সাবঅ্যারের গুণফল বের করব এবং সবগুলো তুলনা করে maxProd বের করব।

#include 
using namespace std;

long calMaxSubSeqProd(int arr[], int n) {
    int smallerLeftEle[n];
    smallerLeftEle[0] = -1;
    set small;
    
    for (int i = 0; i < n; i++) {
        auto it = small.insert(arr[i]);
        auto val = it.first;
        --val;
        if (val != small.end())
            smallerLeftEle[i] = *val;
        else
            smallerLeftEle[i] = -1;
    }
    
    long maxProd = -10000;
    long prod;
    int greaterRightEle = arr[n - 1];
    
    for (int i = n - 2; i >= 1; i--) {
        if (arr[i] > greaterRightEle)
            greaterRightEle = arr[i];
        else if (smallerLeftEle[i] != -1) {
            prod = smallerLeftEle[i] * arr[i] * greaterRightEle;
            if (prod > maxProd)
                maxProd = prod;
        }
    }
    return maxProd;
}

int main() {
    int arr[] = {5, 9, 2, 11, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum product of an increasing subsequence of size 3 is " << calMaxSubSeqProd(arr, n);
    return 0;
}

The maximum product of an increasing subsequence of size 3 is 495