इस समस्या में, हमें n पूर्णांक मानों की एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो सरणी का अधिकतम उत्पाद उपसमुच्चय ढूंढे।
समस्या विवरण
यहां, हमें सरणी के तत्वों के एक उपसमुच्चय के अधिकतम संभव उत्पाद की गणना करने की आवश्यकता है।
उपसमुच्चय (Subset)
एक सरणी sub[] सरणी arr[] का उपसमुच्चय है यदि sub[] के सभी तत्व arr[] में मौजूद हैं।
उदाहरण
इनपुट
arr[] = {4, 5, 2, -1, 3}
आउटपुट
40
व्याख्या
उपसमुच्चय sub[] = {4, 5, 2}
उत्पाद = 4*5*2 = 40
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल और आसान दृष्टिकोण सरणी के सभी संभावित उपसमुच्चय बनाना है। उनके उत्पाद ढूंढना और उनमें से अधिकतम वापस करना।
यह समाधान लागू करने में आसान है लेकिन नेस्टेड लूप की आवश्यकता होती है जिससे इसकी जटिलता O(n²*n) क्रम की हो जाती है।
प्रभावी समाधान सरणी से ऋणात्मक (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 को छोड़कर ऋणात्मक है। maxProd = 0।
एल्गोरिदम
आरंभीकरण -
maxProd = 1;
चरण 1 -
सरणी को लूप करें और गिनें, nof0(शून्यों की संख्या) और nofNeg(ऋणात्मक की संख्या), और maxProd ढूंढें। maxProd = maxProd*arr[i], i → 0 से n-1 तक
चरण 2 -
निम्नलिखित मामलों पर विचार करें - केस 1 - if(nofNeg%2 == 0): maxProd केस 2 - if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg) केस 3 - if(nof0 == (n-1) and nofNeg == 1), maxProd = 0।
चरण 3
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
