Maximum product sub-array

Problem

Given an integer array with negative numbers and zero find the subarray with maximum product, i.e. find the contiguous array elements that produce maximum product.
Also find the sub array.

Example
For 7 -3 -1 2 -40 0 3 6, the max subarray product = -1 * 2 * -40 = 80
For -3 7 2 0 -5 7 -2 -2 2, the maximum subarraproduct = -5 * 7 * -2 = 70

Solution

Wherever there is 0 that splits the array into subarrays. We need to find the maximum product of these subarrays individually and return the largest product. Inside this subproblem if there are even number of negative elements then maximum product is the complete product of the array. If there are odd number of negative elements, then make two subarrays once leaving the leftmost negative element and once leaving the rightmost negative element. The maximum of these two products will be returned.

java code

// Returns the product of max product subarray.  Assumes that the
//   given array always has a subarray with product more than 1 
public static int maxSubarrayProduct(int arr[])
{
 int n = arr.length;
    // max positive product ending at the current position
    int maxEndingHere = 1;
 
    // min negative product ending at the current position
    int minEndingHere = 1;
 
    // Initialize overall max product
    int maxSoFar = 1;
 
    // Traverse throught the array. 
    // Following values are maintained after the ith iteration:
     //  maxEndingHere is always 1 or some positive product ending with arr[i]
     //  minEndingHere is always 1 or some negative product ending with arr[i] 
    for (int i = 0; i < n; i++)
    {
        // If this element is positive, update maxEndingHere. Update
        //   minEndingHere only if minEndingHere is negative 
        if (arr[i] > 0)
        {
            maxEndingHere = maxEndingHere*arr[i];
            minEndingHere = Math.min(minEndingHere * arr[i], 1);
        }
 
        // If this element is 0, then the maximum product cannot
        //   end here, make both maxEndingHere and minEndingHere 0
        //   Assumption: Output is alway greater than or equal to 1. 
        else if (arr[i] == 0)
        {
            maxEndingHere = 1;
            minEndingHere = 1;
        }
 
        // If element is negative. This is tricky
        //   maxEndingHere can either be 1 or positive. 
        //   minEndingHere can either be 1
        //   or negative.
        //   next minEndingHere will always be prev. maxEndingHere * arr[i]
        //   next maxEndingHere will be 1 if prev minEndingHere is 1, otherwise
        //   next maxEndingHere will be prev minEndingHere * arr[i] 
        else
        {
            int temp = maxEndingHere;
            maxEndingHere = Math.max (minEndingHere * arr[i], 1);
            minEndingHere = temp * arr[i];
        }
 
        // update maxSoFar, if needed
        if (maxSoFar <  maxEndingHere)
          maxSoFar  =  maxEndingHere;
    }
 
    return maxSoFar;
}

Time Complexity: O(n)
Auxiliary Space: O(1)

Dry running the algo
Consider the array A = {1, -2, -3, 0, 7, -8, -2}.
Initially we will take maxSoFar, maxEndingHere and minEnding here as 1, as we have to multiply by the number. Also, we have to reset maxEndingHere and minEndingHere to 1, whenever we encounter 0.

Now, we iterate over the array
i=0, a[i] > 0 implies we have to multiply maxEndingHere=1*1 = 1, minEndingHere = 1.Finally maxSoFar stays the same.

i = 1, a[i] = -2 < 0 which implies temp= maxEndingHere = 1. MaxEndingHere = max(-2* 1, 1) =1 , and maxEndingHere =  1 * -2 = -2

i = 2, maxEndingHere = 6, minEndingHere = -3, maxSoFar = 6

i = 3 , maxEndingHere = 1, minEndingHere = 1, maxSoFar = 6

and so on.

Github link - https://github.com/kinshuk4/AlgorithmUtil/blob/master/DynamicProgProblem/src/com/vaani/algo/subarray/MaxProductSubArray.java

References

• http://www.geeksforgeeks.org/maximum-product-subarray/
• http://stackoverflow.com/questions/18839769/the-max-product-of-consecutive-elements-in-an-array