maximumProductSubarray.cpp

/*Given an array Arr that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.

Example 1:
Input: N = 5    Arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is  6, -3, -10 which gives product as 180.
Example 2:
Input: N = 6    Arr[] = {2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is 2, 3, 4, 5 which gives product as 120. */


class Solution{
public:

	// Function to find maximum product subarray
	long long maxProduct(int *arr, int n) {
	    if(n==1)
	        return arr[0];
	    //ma-maximum element in array
	    long long ma=arr[0];
	    //mi-minimum element in array
	    long long mi=arr[0];
	    //prod-max product in an array
	    long long prod=arr[0];
	    //traversing from 2nd element to last element
	    for(int i=1;i<n;i++)
	    {
	        //if current element is negatiuve
	        if(arr[i]<0)
	            swap(ma,mi);
	       //select maximum between product and current element
	       ma=max((long long) arr[i],arr[i]*ma);
	       //select minimum between product and current element
	       mi=min((long long) arr[i],arr[i]*mi);
	       //if product greater than maximumProduct then save it
	       if(ma>prod)
	        prod=ma;
	    }
	    return prod;
	}
};