এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে arr[]। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে বাম এবং ডানে পরবর্তী বৃহত্তর সূচকগুলির সর্বাধিক গুণফল গণনা করা যায়৷
সমস্যা বর্ণনা −
প্রদত্ত অ্যারের জন্য আমাদের বাম[i]*right[i]-এর সর্বোচ্চ মানের গুণফল খুঁজে বের করতে হবে। উভয় অ্যারেকে −
হিসাবে সংজ্ঞায়িত করা হয়েছেleft[i] = j, such that arr[i] <’. ‘ arr[j] and i > j. right[i] = j, such that arr[i] < arr[j] and i < j. *The array is 1 indexed.
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[6] = {5, 2, 3, 1, 8, 6} আউটপুট
15
ব্যাখ্যা
Creating left array,
left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Index products :
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
সমাধান পদ্ধতি −
উপাদানটির বাম এবং ডানদিকে একটি বৃহত্তর উপাদানের সূচকের সর্বাধিক গুণফল খুঁজে পেতে। আমরা প্রথমে বাম এবং ডানের সূচীগুলি খুঁজে বের করব এবং তুলনা করার জন্য তাদের পণ্য সংরক্ষণ করব।
এখন, বাম এবং ডানের সর্বশ্রেষ্ঠ উপাদান খুঁজে বের করার জন্য, আমরা বাম এবং ডানদিকে সূচীর মানের বৃহত্তর উপাদানগুলির জন্য একে একে পরীক্ষা করব। খুঁজতে আমরা স্ট্যাক ব্যবহার করব। এবং নিম্নলিখিত অপারেশনগুলি করুন,
If stack is empty −> push current index, tos = 1. Tos is top of the stack Else if arr[i] > arr[tos] −> tos = 1.
এটি ব্যবহার করে আমরা অ্যারের বাম এবং ডানের দেওয়া উপাদানের চেয়ে বড় সমস্ত উপাদানের সূচক মান খুঁজে পেতে পারি।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
int* findNextGreaterIndex(int a[], int n, char ch ) {
int* greaterIndex = new int [n];
stack<int> 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
