समस्या में, हमें n पूर्णांक मानों का एक सरणी arr[] दिया जाता है। हमारा काम किसी सरणी के अधिकतम उत्पाद सबसेट को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - यहां, हमें किसी सरणी के तत्वों के सबसेट के अधिकतम संभव उत्पाद की गणना करने की आवश्यकता है।
सबसेट - एक सरणी उप [] सरणी गिरफ्तारी का एक सबसेट है [] यदि उप [] के सभी तत्व गिरफ्तारी [] में मौजूद हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 5, 2, −1, 3} आउटपुट
40
स्पष्टीकरण
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40 समाधान दृष्टिकोण
समस्या को हल करने का एक सरल और आसान तरीका है, सरणी के सभी संभावित सबसेट बनाना। उनके उत्पाद ढूंढें और उनमें से अधिकतम लौटाएं।
इस समाधान को लागू करना आसान है, लेकिन इसके लिए नेस्टेड लूप की आवश्यकता होती है, जो O(n 2 के क्रम की जटिलता को बढ़ाता है। *एन)।
यहां कार्यान्वयन का प्रयास करें।
प्रभावी समाधान सरणी से ऋणात्मक (nofNeg) और शून्य (nof0) की संख्या की गणना करके और फिर इन शर्तों के आधार पर maxProd की गणना करें।
केस 1 (nof0 =0 और nofNeg सम है)− उत्पाद में सरणी के सभी तत्वों पर विचार करें।
maxProd =arr[0] * arr[1] * … arr[n−1]
केस 2 (nof0 =0 और nofNeg विषम है) - सरणी के सबसे बड़े ऋणात्मक तत्व (0 के निकटतम) को छोड़कर सरणी के सभी तत्वों पर विचार करें।
केस 3 (nof0 !=0)− उत्पाद के लिए सरणी के सभी शून्य छोड़ दें। और मामले 1 और 2 के समान मामलों को लें।
विशेष मामला - 0 को छोड़कर केवल एक तत्व ऋणात्मक है। मैक्सप्रोड =0.
एल्गोरिदम
आरंभ करें -
maxProd = 1;
चरण 1 -
Loop the array and count, nof0(number of zeros) and nofNeg(number of negatives), and find maxProd. maxProd = maxProd*arr[i], i −> 0 to n−1खोजें।
चरण 2 -
consider the following cases − Case 1− if(nofNeg%2 == 0): maxProd Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg) Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.
चरण 3
Print maxProd.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
int larNeg = −1000;
int nofNeg = 0, Nof0 = 0;
int maxProd = 1;
for (int i = 0; i < n; i++) {
if (arr[i] == 0){
Nof0++;
continue;
}
else if (arr[i] < 0) {
nofNeg++;
if(larNeg < arr[i])
larNeg = arr[i];
}
maxProd = maxProd * arr[i];
}
if(nofNeg%2 == 0){
return maxProd;
}
else if(nofNeg%2 != 0)
return (maxProd / larNeg);
if(Nof0 == (n−1) and nofNeg == 1)
return 0;
return maxProd;
}
int main(){
int arr[] = {4, −2, 5, −1, 3, −6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
return 0;
} आउटपुट
The maximum product subset of an array is 720