इस समस्या में, हमें n पूर्णांकों से युक्त एक सरणी arr[] दी गई है। हमारा काम सरणी में एक ट्रिपल (आकार 3 के बाद के) के अधिकतम उत्पाद को खोजना है। यहां, हम अधिकतम उत्पाद मूल्य के साथ ट्रिपल ढूंढेंगे और फिर उत्पाद वापस कर देंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {9, 5, 2, 11, 7, 4} आउटपुट
693
स्पष्टीकरण
यहां, हम त्रिक पाएंगे जो सरणी के सभी तत्वों का अधिकतम उत्पाद देता है। मैक्सप्रोड =9 * 11 * 7 =693
समाधान दृष्टिकोण
समस्या के कई समाधान हो सकते हैं। हम यहां उनकी चर्चा करेंगे,
विधि 1
प्रत्यक्ष विधि इस विधि में, हम सीधे सरणी के माध्यम से लूप करेंगे और फिर सभी संभावित त्रिक पाएंगे। प्रत्येक त्रिक के तत्वों का गुणनफल खोजें और उनमें से अधिकतम लौटाएँ।
एल्गोरिदम
आरंभ करें
maxProd = −1000
चरण 1 :
Create three nested loops: Loop 1:i −> 0 to n−3 Loop 2: j −> i to n−2 Loop 3: k −> j to n−1
चरण 1.1 -
Find the product, prod = arr[i]*arr[j]*arr[k].
चरण 1.2 -
if prod > maxProd −> maxProd = prod.
चरण 3 -
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++)
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[1], arr[2])
हम इन तीनों का अधिकतम उत्पाद लौटा देंगे।
एल्गोरिदम
चरण 1 -
Sort the given array in descending order.
चरण 2 -
Find product of triples, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
चरण 3 -
if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1
चरण 4 -
else −> return 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;
} आउटपुट
सरणी में ट्रिपलेट का अधिकतम उत्पाद 693
. हैविधि 3
ट्रिपलेट मान ढूँढना।
जैसा कि अब हम जानते हैं कि अधिकतम उत्पाद ट्रिपलेट दोनों में से किसी एक से हो सकता है,
(maximum, second_max, third_max) (maximum, minimum, second_min)
इसलिए, हम सरणी को पार करके इन मानों को सीधे ढूंढ सकते हैं, और फिर मानों का उपयोग करके, हम अधिकतम उत्पाद ट्रिपलेट पाएंगे।
एल्गोरिदम
आरंभ करें
अधिकतम =-1000, secMax =-1000, तीसरा अधिकतम =-1000, न्यूनतम =10000, secMin =10000
चरण 1 -
loop the array i −> 0 to 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.4 -
elseif(arr[i] < secMin) −> secMin = arr[i]
चरण 2 -
triplet1 = max * secMax * thridMax triplet2 = max * min * secMin
चरण 3 -
if(triplet1 > triplet2) −> return triplet1
चरण 4 -
else −> return 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