C++-এ অ্যারেতে বাম ও ডান পাশের नेक्सট ग्रেটার ইন্ডেক্সের গুণফলের সর্বোচ্চ মান বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে দেওয়া থাকলে, প্রতিটি এলিমেন্টের জন্য বাম পাশে সবচেয়ে নিকটের বড় এলিমেন্টের ইন্ডেক্স (L) এবং ডান পাশে সবচেয়ে নিকটের বড় এলিমেন্টের ইন্ডেক্স (R) বের করুন। তারপর L×R-এর সর্বোচ্চ মান খুঁজে বের করুন।

সমাধানের পদ্ধতি (Monotonic Stack)

1. বাম পাশের नेक्सট গ্রেটার: রাইট থেকে লেফ্ট স্ক্যান করুন, স্ট্যাক ব্যবহার করুন।
2. ডান পাশের नेक्सট গ্রেটার: লেফ্ট থেকে রাইট স্ক্যান করুন, স্ট্যাক ব্যবহার করুন।
3. প্রতিটি ইন্ডেক্সের জন্য L×R ক্যালকুলেট করুন এবং সর্বোচ্চ নিন।

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

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

#define MAX 1000

vector nextGreaterInLeft(int a[], int n) {
    vector left_index(MAX, 0);
    stack s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top(); s.pop();
            left_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return left_index;
}

vector nextGreaterInRight(int a[], int n) {
    vector right_index(MAX, 0);
    stack s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top(); s.pop();
            right_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return right_index;
}

int LRProduct(int arr[], int n) {
    vector left = nextGreaterInLeft(arr, n);
    vector right = nextGreaterInRight(arr, n);
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, left[i] * right[i]);
    }
    return ans;
}

int main() {
    int arr[] = {5, 4, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << LRProduct(arr, n);
    return 0;
}

আউটপুট

8

ব্যাখ্যা

অ্যারে: [5,4,3,4,5] (1-বেসড ইন্ডেক্স)

ইন্ডেক্স 3 (মান 3): L=2 (মান 4), R=4 (মান 4) → 2×4=8 (সর্বোচ্চ)

জটিলতা

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