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

সমস্যা বিবরণ

পজেটিভ ইন্টিজার অ্যারে দেওয়া থাকলে, আকার ৩ এর ক্রমবর্ধমান সাবসিকোয়েন্স (a < b < c) খুঁজে বের করুন যাতে a×b×c সর্বোচ্চ হয়।

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

1. smaller[i] = ইন্ডেক্স i-এর বামপাশে থাকা সবচেয়ে বড় মান যা arr[i]-এর চেয়ে ছোট। (সেট ব্যবহার করে O(log n) তে)।
2. ডান পাশ থেকে ট্রাভার্স করুন, max_right রাখুন।
3. প্রতি i-এর জন্য: যদি smaller[i] != -1 হয়, তবে result = max(result, smaller[i] * arr[i] * max_right)।

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

#include <bits/stdc++.h>
using namespace std;

long long int maxProduct(int arr[], int n) {
    int smaller[n];
    smaller[0] = -1;
    set S;
    for (int i = 0; i < n; i++) {
        auto j = S.insert(arr[i]);
        auto itc = j.first;
        --itc;
        if (itc != S.end())
            smaller[i] = *itc;
        else
            smaller[i] = -1;
    }
    long long int result = LLONG_MIN;
    int max_right = arr[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        if (arr[i] > max_right)
            max_right = arr[i];
        else if (smaller[i] != -1)
            result = max(result, 1LL * smaller[i] * arr[i] * max_right);
    }
    return result;
}

int main() {
    int arr[] = {10, 11, 9, 5, 6, 1, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxProduct(arr, n) << endl;
    return 0;
}

আউটপুট

2200

ব্যাখ্যা

সাবসিকোয়েন্স: 10, 11, 20 → গুণফল = 2200

জটিলতা

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