हमें आकार N की एक पूर्णांक सरणी दी गई है। यहां लक्ष्य अधिकतम और न्यूनतम उत्पाद उपसमुच्चय ढूंढना है। हम इसे दो उत्पाद चरों का उपयोग करके करेंगे, एक अब तक पाए गए न्यूनतम उत्पाद minProd के लिए और दूसरा अब तक पाए गए अधिकतम उत्पाद maxProd के लिए।
सरणी को पार करते समय हम प्रत्येक तत्व को minProd और maxProd दोनों से गुणा करेंगे। साथ ही पिछले अधिकतम उत्पाद, पिछले न्यूनतम उत्पाद, वर्तमान अधिकतम उत्पाद, वर्तमान न्यूनतम उत्पाद और वर्तमान तत्व पर नज़र रखेंगे।
इनपुट
Arr[]= { 1,2,5,0,2 }
आउटपुट
अधिकतम उत्पाद: 20 न्यूनतम उत्पाद: 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 }
आउटपुट
अधिकतम उत्पाद: 20 न्यूनतम उत्पाद: -20
व्याख्या - अधिकतम उत्पाद के लिए, उपसमुच्चय के तत्व हैं - { -1,2,-5,2 }
न्यूनतम उत्पाद के लिए, उपसमुच्चय के तत्व हैं - { 2,-5,2 }
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
पूर्णांक सरणी Arr[] में धनात्मक और ऋणात्मक पूर्णांक होते हैं।
चर size सरणी की लंबाई रखता है।
फ़ंक्शन getProductSubset(int arr[], int n) सरणी को इनपुट के रूप में लेता है और प्राप्त तत्वों के अधिकतम और न्यूनतम उत्पाद को लौटाता है।
चर curMin, curMax वर्तमान अधिकतम और न्यूनतम उत्पाद को संग्रहीत करने के लिए उपयोग किए जाते हैं। प्रारंभ में arr[0]।
चर prevMin, prevMax पिछले अधिकतम और न्यूनतम उत्पाद को संग्रहीत करने के लिए उपयोग किए जाते हैं। प्रारंभ में arr[0]।
चर maxProd और minProd अंतिम अधिकतम और न्यूनतम उत्पादों को संग्रहीत करने के लिए उपयोग किए जाते हैं।
सरणी को दूसरे तत्व arr[1] से अंतिम सूचकांक तक पार करना शुरू करें।
अधिकतम उत्पाद के लिए, वर्तमान arr[i] को prevMax और prevMin से गुणा करें। अधिकतम उत्पाद को curMax में संग्रहीत करें। यदि यह curMax > prevMax है, तो curMax को prevMax से अद्यतन करें।
यदि curMax > maxProd है तो maxProd को curMax से अद्यतन करें।
अगले पुनरावृत्ति के लिए prevMax को curMax से अद्यतन करें।
तुलनाओं को बदलकर prevMin, curMin और minProd के लिए भी यही चरण करें।
लूप समाप्त होने के बाद maxProd और minProd में प्राप्त परिणाम प्रिंट करें।
उदाहरण
#include <iostream> using namespace std; void getProductSubset(int arr[], int n){ // सभी उत्पादों को 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; // arr[0] के बाद सभी तत्वों को संसाधित करें for (int i = 1; i < n; ++i){ /* वर्तमान अधिकतम उत्पाद निम्नलिखित में से अधिकतम है 1) prevMax * वर्तमान arr[i] (जब arr[i] धनात्मक है) 2) prevMin * वर्तमान arr[i] (जब arr[i] ऋणात्मक है) 3) वर्तमान arr[i] 4) पिछला अधिकतम उत्पाद */ 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; /* वर्तमान न्यूनतम उत्पाद निम्नलिखित में से न्यूनतम है 1) prevMin * वर्तमान arr[i] (जब arr[i] धनात्मक है) 2) prevMax * वर्तमान arr[i] (जब arr[i] ऋणात्मक है) 3) वर्तमान arr[i] 4) पिछला न्यूनतम उत्पाद */ 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; // अगली पुनरावृत्ति के लिए वर्तमान मानों को पिछले मानों में कॉपी करें prevMax = curMax; prevMin = curMin; } std::cout<<"अधिकतम उपसमुच्चय उत्पाद: "<<maxProd; std::cout<<"\nन्यूनतम उपसमुच्चय उत्पाद: "<<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; }
आउटपुट
अधिकतम उपसमुच्चय उत्पाद: 192 न्यूनतम उपसमुच्चय उत्पाद: -64
