इस समस्या में, हमें एक ऐरे एरर [] दिया जाता है। हमारा काम बाएँ और दाएँ पर अगले बड़े की अनुक्रमणिका के अधिकतम उत्पाद की गणना करने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण -
दिए गए सरणी के लिए हमें बाएँ [i] * दाएँ [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