এই টিউটোরিয়ালে, আমরা বাম এবং ডানে পরবর্তী বৃহত্তর সূচকের সর্বাধিক পণ্য খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হবে। আমাদের কাজ হল সর্বাধিক বাম-ডান পণ্য (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
