বাম ও ডান পাশে পরবর্তী বড় উপাদানের ইনডেক্স গুণফলের সর্বোচ্চ মান (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল বাম ও ডান পাশে পরবর্তী বড় উপাদানের ইনডেক্স গুণফলের সর্বোচ্চ মান বের করার প্রোগ্রাম তৈরি করা।

দেওয়া অ্যারেতে left[i]*right[i]-এর সর্বোচ্চ মান বের করতে হবে। দুটি অ্যারে নিচের মতো সংজ্ঞায়িত:

left[i] = j, যেন arr[i] < arr[j] এবং i > j।
right[i] = j, যেন arr[i] < arr[j] এবং i < j।
*অ্যারেটি ১-ইনডেক্সড।

arr[6] = {5, 2, 3, 1, 8, 6}

15

left অ্যারে তৈরি: left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
ইনডেক্স গুণফল:
1 → 0*5 = 0
2 → 1*3 = 3
3 → 1*5 = 5
4 → 3*5 = 15
5 → 0*0 = 0
6 → 0*5 = 0

সর্বোচ্চ গুণফল = 15

একটি উপাদানের বাম ও ডান পাশে বড় উপাদানের ইনডেক্স গুণফলের সর্বোচ্চ মান বের করার জন্য, আমরা প্রথমে বাম ও ডান পাশের বড় উপাদানের ইনডেক্স বের করে তাদের গুণফল সংরক্ষণ করব तুলনার জন্য।

এখন, বাম ও ডান পাশের বড় উপাদান বের করার জন্য, আমরা এক-এক করে বাম ও ডান পাশের ইনডেক্স মান চেক করব বড় উপাদানের জন্য। খুঁজে বের করতে আমরা স্ট্যাক (stack) ব্যবহার করব এবং নিচের অপারেশনগুলো করব:

যদি স্ট্যাক খালি হয় → বর্তমান ইনডেক্স পুশ করুন, tos = 1।
অন্যথায় যদি arr[i] > arr[tos] হয় → tos = 1।

এই পদ্ধতিতে আমরা বাম ও ডান পাশে দেওয়া উপাদানের চেয়ে বড় সব উপাদানের ইনডেক্স মান বের করতে পারব।

#include 
using namespace std;

int* findNextGreaterIndex(int a[], int n, char ch) {
    int* greaterIndex = new int[n];
    stack index;
    
    if (ch == 'R') {
        for (int i = 0; i < n; ++i) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    } else if (ch == 'L') {
        for (int i = n - 1; i >= 0; i--) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    }
    return greaterIndex;
}

int calcMaxGreaterIndedxProd(int arr[], int n) {
    int* left = findNextGreaterIndex(arr, n, 'L');
    int* right = findNextGreaterIndex(arr, n, 'R');
    int maxProd = -1000;
    int prod;
    
    for (int i = 1; i < n; i++) {
        prod = left[i] * right[i];
        if (prod > maxProd)
            maxProd = prod;
    }
    return maxProd;
}

int main() {
    int arr[] = { 5, 2, 3, 1, 8, 6 };
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << "The maximum product of indexes of next greater on left and right is " << calcMaxGreaterIndedxProd(arr, n);
    return 0;
}

The maximum product of indexes of next greater on left and right is 15