C++ में अधिकतम गुणनफल सबअरे | नकारात्मक गुणनफल मामला जोड़ा गया

इस समस्या में, हमें पूर्णांकों की एक सरणी (सकारात्मक और नकारात्मक दोनों) दी गई है। हमारा कार्य C++ में अधिकतम गुणनफल सबअरे की गणना करने के लिए एक प्रोग्राम बनाना है।

समस्या समाधान - यहां, हमारे पास एक सरणी है जिसमें सकारात्मक, नकारात्मक, और शून्य संख्याएं हैं। हमें सरणी के तत्वों द्वारा बनाए गए सबअरे का गुणनफल ढूंढना है। और सबअरे के गुणनफल को अधिकतम करना है।

आइए एक उदाहरण से समस्या को समझते हैं,

इनपुट

arr[] = {-1, 2, -7, -5, 12, 6}

आउटपुट

5040

व्याख्या

अधिकतम गुणनफल वाला सबअरे है {2, -7, -5, 12, 6}

Product = 5040

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए, हमें एक सरणी दी गई है और सबअरे का अधिकतम गुणनफल और maxVal प्रबंधित करना है जो वर्तमान तत्व तक अधिकतम गुणनफल है और minVal गुणनफल का नकारात्मक अधिकतम है। फिर वर्तमान मान के आधार पर, maxVal और minVal को निम्नानुसार अपडेट किया जाता है:

केस 1 - तत्व सकारात्मक है - सरणी से गुणा करके maxVal और minVal को अपडेट करें।

केस 2 - तत्व शून्य है - वर्तमान सबअरे को तोड़ें क्योंकि 0 से गुणा करने पर 0 होगा।

केस 3 - तत्व नकारात्मक है - दोनों मानों को नकारात्मक मानों के साथ अपडेट करें जिससे इसका अधिकतम बने।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

उदाहरण

#include <iostream> 
using namespace std; 
int min(int a, int b){ 
    if(a < b) 
        return a; 
    return b; 
} 
int max(int a, int b){ 
    if(a > b) 
        return a; 
    return b; 
} 
int CalcMaxProductSubArray(int arr[], int n) { 
    int i = 0; 
    int maxVal = -1000; 
    int localMax = 1; 
    int localMin = 1; 
    int lastMax; 
    while(i < n) { 
        int currentVal = arr[i]; 
        if (currentVal > 0) { 
            localMax = (localMax * currentVal); 
            localMin = min(1, localMin * currentVal); 
        } 
        else if (currentVal < 0) { 
            lastMax = localMax; 
            localMax = (localMin * currentVal); 
            localMin = (lastMax * currentVal); 
        } else { 
            localMin = 1; 
            localMax = 0; 
        } 
        maxVal = max(maxVal, localMax); 
        if (localMax <= 0) 
            localMax = 1; 
        i++; 
    } 
    return maxVal; 
} 
int main(){ 
    int arr[] = { -1, 2, -7, -5, 12, 6 }; 
    int n = 6; 
    cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n); 
    return 0; 
}

आउटपुट

The maximum product Subarray is 5040