C++ में आकार k के सबसीक्वेंस का अधिकतम गुणनफल

इस समस्या में, हमें पूर्णांकों की एक सरणी arr[] और एक संख्या 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