हमें आकार N के पूर्णांकों की एक सरणी दी गई है। यहाँ लक्ष्य अधिकतम और न्यूनतम उत्पाद सबसेट को खोजना है। हम दो उत्पाद चर लेकर ऐसा करेंगे, एक न्यूनतम उत्पाद के लिए जो अब तक मिला है minProd और दूसरा अब तक मिले अधिकतम उत्पाद के लिए, maxProd।
सरणी को पार करते समय हम प्रत्येक तत्व को minProd और maxProd दोनों से गुणा करेंगे। पिछले अधिकतम उत्पाद, पिछले न्यूनतम उत्पाद, वर्तमान अधिकतम उत्पाद, वर्तमान न्यूनतम उत्पाद और वर्तमान तत्व पर भी नज़र रखें।
इनपुट
Arr[]= { 1,2,5,0,2 } आउटपुट
Maximum Product: 20 Minimum Product: 0
स्पष्टीकरण - सरणी में दूसरे तत्व से शुरू होकर maxProd और minProd मानों के साथ 1 (प्रथम तत्व) के साथ आरंभ किया गया।
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
इनपुट
Arr[]= { -1,2,-5,0,2 } आउटपुट
Maximum Product: 20 Minimum Product: -20
स्पष्टीकरण - अधिकतम उत्पाद के लिए, सबसेट में तत्व होते हैं- { -1,2,-5,2 }
न्यूनतम उत्पाद के लिए, सबसेट में तत्व होते हैं- { 2,-5,2 }
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी Arr[] में धनात्मक और ऋणात्मक पूर्णांक होते हैं।
-
चर आकार में सरणी की लंबाई होती है।
-
फ़ंक्शन getProductSubset(int arr[], int n) सरणी को इनपुट के रूप में लेता है और प्राप्त तत्वों का अधिकतम और न्यूनतम उत्पाद देता है।
-
वर्तमान अधिकतम और न्यूनतम उत्पाद को संग्रहीत करने के लिए चर curMin, curMax का उपयोग किया जाता है। प्रारंभ में गिरफ्तार [0]।
-
वेरिएबल्स prevMin, prevMax का उपयोग पिछले अधिकतम और न्यूनतम उत्पाद को प्राप्त करने के लिए किया जाता है। प्रारंभ में गिरफ्तार [0]।
-
चर maxProd और minProd का उपयोग अंतिम अधिकतम और न्यूनतम प्राप्त उत्पादों को संग्रहीत करने के लिए किया जाता है।
-
दूसरे एलिमेंट से ऐरे को ट्रैवर्स करना शुरू करें, एआर [1] आखिरी इंडेक्स तक।
-
अधिकतम उत्पाद के लिए, वर्तमान गिरफ्तारी [i] को prevMax और prevMin से गुणा करें। CurMax में अधिकतम उत्पाद स्टोर करें। अगर यह curMax>prevMax, curMax को prevMax के साथ अपडेट करें।
-
maxProd को curMax के साथ अपडेट करें यदि curMax>maxProd।
-
अगले पुनरावृत्ति के लिए curMax के साथ पिछले अद्यतन prevMax पर।
-
तुलनाओं को बदलकर prevMin, curMin और minProd के लिए ऊपर दिए गए चरणों का पालन करें।
-
लूप समाप्त होने के बाद maxProd और minProd में प्राप्त परिणामों को प्रिंट करें।
उदाहरण
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// Initialize all products with arr[0]
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin= arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1=0,temp2=0,temp3=0;
// Process all elements after arr[0]
for (int i = 1; i < n; ++i){
/* Current maximum product is maximum of following
1) prevMax * current arr[i] (when arr[i] is +ve)
2) prevMin * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous max product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1>temp2?temp1:temp2;
curMax = temp3>arr[i]?temp3:arr[i];
curMax = curMax>prevMax?curMax:prevMax;
/* Current minimum product is minimum of following
1) prevMin * current arr[i] (when arr[i] is +ve)
2) prevMax * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous min product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1<temp2?temp1:temp2;
curMin = temp3<arr[i]?temp3:arr[i];
curMin = curMin<prevMin?curMin:prevMin;
maxProd = maxProd>curMax?maxProd:curMax;
minProd = minProd<curMin?minProd:curMin;
// copy current values to previous values
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
} आउटपुट
Maximum Subset Product: 192 Minimum Subset Product: -64