इस समस्या में, हमें एक सरणी arr[] दी गई है। हमारा कार्य C++ में सरणी में अधिकतम गुणनफल क्वाड्रपल (आकार 4 का सब-सीक्वेंस) ढूंढने के लिए एक प्रोग्राम बनाना है।
कोड विवरण - यहां, हमें एक क्वाड्रपल (आकार 4 का सब-सीक्वेंस) ढूंढना है जैसे कि सभी तत्वों का गुणनफल अधिकतम हो।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
arr[] = {4, -2, 5, -6, 8}
आउटपुट
840
व्याख्या
क्वाड्रपल, (-3, 5, -7, 8) जिसका गुणनफल 840 है।
समाधान दृष्टिकोण
दिए गए समस्या के कई समाधान हो सकते हैं।
एक सरल समाधान सरणी को पार करके सीधी विधि का उपयोग करना है। फिर सरणी में सभी संभावित क्वाड्रपल ढूंढना। उनका गुणनफल ढूंढना और फिर अधिकतम गुणनफल क्वाड्रपल खोजने के लिए तुलना करना।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n){
int maxProd = 0;
int prod = 1;
for (int i = 0; i <= n - 4; i++)
for (int j = i + 1; j <= n - 3; j++)
for (int k = j + 1; k <= n - 2; k++)
for (int l = k + 1; l <= n - 1; l++) {
prod = arr[i] * arr[j] * arr[k] * arr[l];
maxProd = max(maxProd, prod);
prod = 1;
}
return maxProd;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
आउटपुट
Maximum product of quadruple is 480
अधिकतम गुणनफल वाले क्वाड्रपल को खोजने का एक और तरीका सरणी के चार अधिकतम तत्वों और चार न्यूनतम तत्वों को ढूंढना है।
मान लीजिए mx1, mx2, mx3, mx4 पहले चार अधिकतम संख्याएं हैं। और mn1, mn2, mn3, mn4 सरणी की पहली चार न्यूनतम संख्याएं हैं। फिर मान ढूंढें:
1. mx1 * mx2 * mx3 * mx4 2. mn1 * mn2 * mn3 * mn4 3. mx1 * mx2 * mn1 * mn2
और इन तीन गुणनफल मानों में से अधिकतम वापस करें जो अधिकतम गुणनफल क्वाड्रपल देगा। और सभी मामलों पर विचार किया जाता है।
हमारे एल्गोरिदम के कार्यान्वयन को दिखाने वाला प्रोग्राम
उदाहरण
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n) {
int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
for (int i = 0; i < n; i++) {
if(arr[i] < mn1){
mn4 = mn3;
mn3 = mn2;
mn2 = mn1;
mn1 = arr[i];
}
else if(arr[i] < mn2){
mn4 = mn3;
mn3 = mn2;
mn2 = arr[i];
}
else if(arr[i] < mn3){
mn4 = mn3;
mn3 = arr[i];
}
else if(arr[i] < mn4){
mn4 = arr[i];
}
if(arr[i] > mx1){
mx4 = mx3;
mx3 = mx2;
mx2 = mx1;
mx1 = arr[i];
}
else if(arr[i] > mx2){
mx4 = mx3;
mx3 = mx2;
mx2 = arr[i];
}
else if(arr[i] > mx3){
mx4 = mx3;
mx3 = arr[i];
}
else if(arr[i] > mx4){
mx4 = arr[i];
}
}
int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
आउटपुट
Maximum product of quadruple is 480
एक और दृष्टिकोण सरणी को सॉर्ट करना हो सकता है। फिर चार अधिकतम और चार न्यूनतम सरणी के अंत और शुरुआत में होंगे। फिर ऊपर के समाधान की तरह तीन संयोजनों का अधिकतम ढूंढकर हल करें।
हमारे दृष्टिकोण के कार्यान्वयन को दिखाने वाला प्रोग्राम
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
sort(arr, arr + n);
int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] *
arr[1] * arr[2] * arr[3]));
maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
return maxVal;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
आउटपुट
Maximum product of quadruple is 480