अधिकतम उत्पाद सबरे | सी ++ में नकारात्मक उत्पाद केस जोड़ा गया

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

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

5040

स्पष्टीकरण

अधिकतम उत्पाद के साथ उप-सरणी {2, -7, -5, 12, 6}

Product = 5040

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

इस समस्या को हल करने के लिए, हमें एक सरणी और उप-सरणी का अधिकतम उत्पाद दिया जाता है और अधिकतम वैल का प्रबंधन करता है जो वर्तमान तत्व तक अधिकतम उत्पाद है और न्यूनतम वैल उत्पाद का नकारात्मक अधिकतम है। फिर वर्तमान मान के आधार पर, 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