इस ट्यूटोरियल में, हम बाएँ और दाएँ पर अगले ग्रेटर के इंडेक्स के अधिकतम उत्पाद को खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें पूर्णांकों की एक सरणी प्रदान की जाएगी। हमारा कार्य अधिकतम बाएँ-दाएँ उत्पाद (L(i)*R(i) के साथ तत्व को खोजना है जहाँ L(i) बाईं ओर निकटतम सूचकांक है और वर्तमान तत्व से अधिक है और R (i) दाईं ओर निकटतम सूचकांक है और वर्तमान तत्व से बड़ा)।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
//finding greater element on left side
vector<int> nextGreaterInLeft(int a[], int n) {
vector<int> left_index(MAX, 0);
stack<int> 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;
}
//finding greater element on right side
vector<int> nextGreaterInRight(int a[], int n) {
vector<int> right_index(MAX, 0);
stack<int> 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;
}
//finding maximum LR product
int LRProduct(int arr[], int n) {
vector<int> left = nextGreaterInLeft(arr, n);
vector<int> 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