सरणी दी गई है। प्रत्येक तत्व के लिए बाएं तरफ निकटतम बड़ा तत्व का इंडेक्स L(i) और दाएं तरफ निकटतम बड़ा तत्व का इंडेक्स R(i) खोजें। L(i) * R(i) का अधिकतम मान ज्ञात करें।
स्टैक का उपयोग करके दोनों तरफ के अगले बड़े तत्व O(n) में खोजें।
उदाहरण: {5, 4, 3, 4, 5} → अधिकतम गुणनफल 8।
C++ कार्यान्वयन
#include <bits/stdc++.h> using namespace std; #define MAX 1000 vectornextGreaterInLeft(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