इस समस्या में, हमें पूर्णांकों की एक सरणी गिरफ्तारी [] और एक संख्या k दी जाती है। हमारा कार्य C++ में आकार k के बाद के अधिकतम उत्पाद को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - यहां, हमें आकार k, 1<=k <=n के बाद के क्रम को खोजने की जरूरत है, जिसमें इसके तत्वों का अधिकतम गुणनफल है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {1, 5, 6, -2, 0, 4} , k = 3 आउटपुट
120
स्पष्टीकरण
आकार 3 के बाद जिसका उत्पाद अधिकतम है (5, 6, 4) है। उत्पाद 120 है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए, हम पहले arr [] और फिर arr [] के तत्वों और k के मान के आधार पर सरणी को सॉर्ट करेंगे। निम्नलिखित मामलों में विधि बदल जाती है -
केस 1 (यदि k सम है) - उत्पाद में 0 को छोड़कर सभी अधिकतम k मान हो सकते हैं। यहाँ, हमें ऋणात्मक मान युग्मों पर भी विचार करने की आवश्यकता है। चूँकि उनका परिमाण भी अधिकतम का परिणाम दे सकता है।
केस 2 (यदि k विषम है) - यह थोड़ी जटिल स्थिति है और मान परिभाषित करते हैं कि परिणाम की गणना कैसे की जानी चाहिए। सरणी के अधिकतम तत्व के आधार पर इस मामले को और वर्गीकृत करने की आवश्यकता है।
केस 2.1 (यदि अधिकतम संख्या सकारात्मक है) - इसका मतलब है कि सरणी सकारात्मक और नकारात्मक संख्याओं का मिश्रण है। इस मामले में, हम अधिकतम k तत्व पाएंगे और नकारात्मक पक्ष से अधिकतम जोड़े भी खोजेंगे (यदि संभव हो तो यह परिणाम दे सकता है)।
केस 2.2 (यदि अधिकतम संख्या शून्य है) - इसका मतलब है कि सरणी में सभी नकारात्मक तत्व और शून्य हैं। इस मामले में, अधिकतम परिणाम 0 होगा, क्योंकि विषम संख्या में ऋणात्मक तत्वों को गुणा करने पर एक ऋणात्मक संख्या प्राप्त होगी, जिसका अर्थ है कि 0 अधिकतम गुणनफल है।
केस 2.3 (यदि अधिकतम संख्या नकारात्मक है) - इसका मतलब है कि सरणी में केवल ऋणात्मक संख्याएँ हैं। इस मामले में, न्यूनतम परिमाण वाले तत्वों को गुणा करके अधिकतम परिणाम प्रदान किया जाएगा यानी अधिकतम सरणी मदद करेगी।
इस तरह, हमें तत्वों के मूल्य के साथ-साथ k पर भी जांच रखने की आवश्यकता है। इष्टतम परिणाम के लिए। इसके लिए, हम यह जांचने के लिए अधिकतम और न्यूनतम दोनों पक्षों को सरणी में रखेंगे कि क्या परिणाम में नकारात्मक युग्मों को गुणा करके परिणाम प्राप्त किया जा सकता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
} आउटपुट
The maximum product of subsequence of size 3 is 120