इस समस्या में, हमें पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य C++ में दो ट्रैवर्सल का उपयोग करके अधिकतम गुणनफल सबअरे खोजने के लिए एक प्रोग्राम बनाना है।
समस्या विवरण - यहां सरणी में, हम दो ट्रैवर्सल का उपयोग करके अधिकतम गुणनफल सबअरे ढूंढेंगे: एक इंडेक्स 0 से और दूसरा इंडेक्स (n-1) से।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
arr[] = {4, -2, 5, -6, 0, 8}
आउटपुट
240
उदाहरण
Subarray = {4, -2, 5, -6} Maximum product = 4 * (-2) * 5 * (-6) = 240
समाधान दृष्टिकोण
दो ट्रैवर्सल का उपयोग करके इस समस्या को हल करने के लिए। यहां, हम बाएं से दाएं ट्रैवर्सल यानी इंडेक्स 0 से n-1 के लिए दो स्थानीय अधिकतम मानों का उपयोग करके अधिकतम गुणनफल ढूंढेंगे। और एक दाएं से बाएं ट्रैवर्सल यानी इंडेक्स n-1 से 0 के लिए। बाकी एल्गोरिदम अधिकतम गुणनफल सबअरे खोजने जैसा ही है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
int frntMax = 1, rearMax = 1, maxVal = 1;
for (int i=0; i<n; i++) {
frntMax = frntMax*arr[i];
if (frntMax == 0)
frntMax = 1;
}
for (int i=n-1; i>=0; i--) {
rearMax = rearMax * arr[i];
if (rearMax == 0)
rearMax = 1;
}
maxVal = max(frntMax, rearMax);
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 0, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
}
आउटपुट
Maximum product subarray is 240