इस समस्या में, हमें n पूर्णांकों से युक्त एक सरणी arr[] दी गई है। हमारा कार्य सरणी में ट्रिपलेट (उपअनुक्रम आकार 3) का अधिकतम उत्पाद ढूंढना है। यहां, हम अधिकतम उत्पाद मान देने वाले ट्रिपलेट को ढूंढेंगे और फिर उत्पाद वापस करेंगे।
उदाहरण
इनपुट
arr[] = {9, 5, 2, 11, 7, 4}
आउटपुट
693
व्याख्या
यहां, हम सरणी के सभी तत्वों का अधिकतम उत्पाद देने वाले ट्रिपलेट को ढूंढेंगे। maxProd = 9 * 11 * 7 = 693
समाधान दृष्टिकोण
समस्या के कई समाधान हो सकते हैं। हम यहां उन पर चर्चा करेंगे,
विधि 1
सीधी विधि: इस विधि में, हम सीधे सरणी के माध्यम से लूप करेंगे और फिर सभी संभावित ट्रिपलेट ढूंढेंगे। प्रत्येक ट्रिपलेट के तत्वों का उत्पाद ढूंढें और उन सभी में से अधिकतम वापस करें।
एल्गोरिदम
आरंभीकरण
maxProd = -1000
चरण 1:
तीन नेस्टेड लूप बनाएं: लूप 1: i → 0 से n-3 तक लूप 2: j → i से n-2 तक लूप 3: k → j से n-1 तक
चरण 1.1 -
उत्पाद ढूंढें, prod = arr[i]*arr[j]*arr[k]।
चरण 1.2 -
यदि prod > maxProd → maxProd = prod।
चरण 3 -
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++)
for (int k = j + 1; k < n; k++){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
return maxProd;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
}
आउटपुट
Maximum product of a triplet in array is 693
विधि 2
क्रमबद्ध करना उपयोग करके
इस विधि में, हम सरणी को अवरोही क्रम में क्रमबद्ध करेंगे। क्रमबद्ध सरणी में, अधिकतम उत्पाद ट्रिपलेट इस पर होगा,
(arr[0], arr[1], arr[2]) (arr[0], arr[n-1], arr[n-2])
हम इन ट्रिपलेट के उत्पाद में से अधिकतम वापस करेंगे।
एल्गोरिदम
चरण 1 -
दी गई सरणी को अवरोही क्रम में क्रमबद्ध करें।
चरण 2 -
ट्रिपलेट का उत्पाद ढूंढें, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n-1]*arr[n-2]
चरण 3 -
if( maxTriplet1 > maxTriplet2 ) → maxTriplet1 वापस करें
चरण 4 -
अन्यथा → maxTriplet2 वापस करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
sort(arr, arr + n, greater<>());
int maxTriplet1 = arr[0]*arr[1]*arr[2];
int maxTriplet2 = arr[0]*arr[n-1]*arr[n-2];
if(maxTriplet1 > maxTriplet2)
return maxTriplet1;
return maxTriplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
}
आउटपुट
Maximum product of a triplet in array is 693
विधि 3
ट्रिपलेट मान ढूंढकर
जैसा कि हम अब जानते हैं कि अधिकतम उत्पाद ट्रिपलेट दो ट्रिपलेट में से किसी एक से हो सकता है,
(अधिकतम, दूसरा_अधिकतम, तीसरा_अधिकतम) (अधिकतम, न्यूनतम, दूसरा_न्यूनतम)
तो, हम सरणी को पार करके सीधे इन मानों को ढूंढ सकते हैं, और फिर मानों का उपयोग करके अधिकतम उत्पाद ट्रिपलेट ढूंढेंगे।
एल्गोरिदम
आरंभीकरण
max = -1000, secMax = -1000, thirdMax = -1000 , min = 10000, secMin = 10000
चरण 1 -
सरणी को लूप करें i → 0 से n-1 तक।
चरण 1.1
if(arr[i] > max) → thirdMax = secMax, secMax = max, max = arr[i]
चरण 1.2 -
elseif(arr[i] > secMax) → thirdMax = secMax, secMax = arr[i]
चरण 1.3 -
elseif(arr[i] > thirdMax) → thirdMax = arr[i]
चरण 1.4 -
if(arr[i] < min) → secMin = min, min = arr[i]
चरण 1.5 -
elseif(arr[i] < secMin) → secMin = arr[i]
चरण 2 -
triplet1 = max * secMax * thirdMax triplet2 = max * min * secMin
चरण 3 -
if(triplet1 > triplet2) → triplet1 वापस करें
चरण 4 -
अन्यथा → triplet2 वापस करें
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int max = -1000, secMax = -1000, thirdMax = -1000;
int min = 1000, secMin = 1000;
for (int i = 0; i < n; i++){
if (arr[i] > max){
thirdMax = secMax;
secMax = max;
max = arr[i];
}
else if (arr[i] > secMax){
thirdMax = secMax;
secMax = arr[i];
}
else if (arr[i] > thirdMax)
thirdMax = arr[i];
if (arr[i] < min){
secMin = min;
min = arr[i];
}
else if(arr[i] < secMin)
secMin = arr[i];
}
int triplet1 = max * secMax * thirdMax;
int triplet2 = max * secMin * min;
if(triplet1 > triplet2)
return triplet1;
return triplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
}
आउटपुट
Maximum product of a triplet in array is 693
