Question:

Finding the product of the Maximum Product Subarray

Summary

Suppose we have an array that contains N integers (may be positive, negative, or zero). Using the below code, we will find the product of the maximum product subarray.

Solution:

//User function template for C++

class Solution{

public:

// Function to find maximum product subarray

long long maxProduct(vector<int> arr, int n) {

// code here

long long int maxi = LLONG_MIN;

long long int pref=0, suf = 0;

for(int i=0;i<n;i++){

if(pref == 0){pref = 1;}

if(suf == 0){suf = 1;}

pref *= arr[i];

suf *= arr[n-i-1];

maxi = max({maxi,pref,suf});

}

return maxi;

}

};

Explanation:

Variables Initialization:

maxi: Represents the maximum product, initialized to the minimum possible long long value.

pref and suf: Represent the prefix and suffix products, initially set to 0.

A loop iterates through the array of integers.
If the prefix (pref) encounters a zero, it is reset to 1 to start a new product calculation.
The same applies to the suffix (suf).
The prefix (pref) and suffix (suf) products are continuously updated by multiplying them with the corresponding array elements.
The max function is used to update the maximum product by considering the current prefix, suffix, and the existing maximum.
The final maximum product of the subarray is returned.