इस समस्या में, हमें n धनात्मक पूर्णांकों का एक सरणी arr[] दिया गया है। हमारा कार्य आकार 3 के बढ़ते क्रम के अधिकतम उत्पाद को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - यहां, हमें सरणी के 3 तत्वों के अधिकतम उत्पाद को खोजने की आवश्यकता है जैसे कि वे एक बढ़ते क्रम का निर्माण करते हैं और सरणी सूचकांक भी बढ़ रहे हैं यानी
arr[i]*arr[j]*arr[k] is maximum, arr[i]<arr[j]<arr[k] and i<j<k
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr = {5, 9, 2, 11, 4, 7} आउटपुट
495
स्पष्टीकरण
All subarrays of size 3 satisfying the condition are (5, 9, 11), prod = 5*9*11 = 495 (2, 4, 7), prod = 2*4*7 = 56 Maximum = 495
समाधान दृष्टिकोण
समस्या को हल करने का एक आसान तरीका है, ऐरे को लूप करना और दी गई शर्त को पूरा करने वाले 3 के सभी सब-एरे को ढूंढना।
तत्वों का उत्पाद ढूंढें और सभी उत्पादों को अधिकतम लौटाएं।
एल्गोरिदम
आरंभ करें -
maxProd = −1000
चरण 1 -
Loop i −> 0 to n−3
चरण 1.1 -
Loop j −> i to n−2
चरण 1.1.1 -
if(arr[i]< arr[j]) −> loop k −> j to n−1
चरण 1.1.1.1 -
if(arr[j] < arr[k]) −> find prod = arr[i]*arr[j]*arr[k].
चरण 1.1.1.2 -
if(maxProd > prod) −> maxProd = prod.
चरण 2 -
Return maxProd.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int maxProd = −1000;
int prod;
for (int i = 0; i < n − 2; i++)
for (int j = i + 1; j < n − 1; j++)
if(arr[i] < arr[j]){
for (int k = j + 1; k < n; k++){
if(arr[j] < arr[k]){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
}
}
return maxProd;
}
int main(){
int arr[] = { 5, 9, 2, 11, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum product of an increasing subsequence of size 3
is "<<calcMaxProd(arr, n);
return 0;
} आउटपुट
The maximum product of an increasing subsequence of size 3 is 495
यह समाधान आसान है लेकिन 3 नेस्टेड लूप का उपयोग करता है जो ऑर्डर ओ (एन 3) की समय जटिलता बनाता है। तो, आइए देखते हैं समस्या का कारगर समाधान,
इस समाधान में, हम सरणी के तत्वों को इंडेक्स 1 से n-2 तक लेंगे। और इसे हमारे 3 तत्व सबअरे के मध्य तत्व के रूप में मानें। और फिर सरणी से शेष दो तत्वों को खोजें।
Element smaller than arr[i] in array with index less than i. Element greater than aar[i] in array with index more than i.
सबसे छोटा तत्व एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग करके पाया जाता है और सबसे बड़े के लिए, हम दाएं से बाएं ओर जाएंगे और अधिकतम तत्व को दाईं ओर पाएंगे।
दोनों मानों को खोजने के बाद, हम सबअरे तत्व के उत्पाद को खोज लेंगे और फिर सभी की तुलना करके अधिकतम उत्पाद पाएंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include<bits/stdc++.h>
using namespace std;
long calMaxSubSeqProd(int arr[] , int n) {
int smallerLeftEle[n];
smallerLeftEle[0] = −1 ;
set<int>small ;
for (int i = 0; i < n ; i++) {
auto it = small.insert(arr[i]);
auto val = it.first;
−−val;
if (val != small.end())
smallerLeftEle[i] = *val;
else
smallerLeftEle[i] = −1;
}
long maxProd = −10000;
long prod ;
int greaterRightEle = arr[n−1];
for (int i= n−2 ; i >= 1; i−−) {
if (arr[i] > greaterRightEle)
greaterRightEle = arr[i];
else if (smallerLeftEle[i] != −1){
prod = smallerLeftEle[i]*arr[i]*greaterRightEle;
if(prod > maxProd)
maxProd = prod;
}
}
return maxProd;
}
int main() {
int arr[] = {5, 9, 2, 11, 4, 7};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product of an increasing subsequence of size 3
is "<<calMaxSubSeqProd(arr, n);
return 0;
} आउटपुट
The maximum product of an increasing subsequence of size 3 is 495