152. Maximum Product Subarray Leetcode Java

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

It is a similar but more difficult problem of 53. maximum subarray. 

We will use the same technique, local and global technique. Please refer problem 53. maximum subarray for more information.

The difference is that when we do the summation, only positive number will make the final result better, while negative won't, so that, we can reset the sum to 0, rather than use the aggregated negative number. 

But for production, it is also possible that a negative number multiply another negative number to make the product very big.

So we need to maintain not only the biggest product till current element(local max, must use current element), but also the minimum as well. Because the minimum one(possibly the most negative number) multiply the current number(possibly a negative number) will become the maximum product so far. 
The recursion equation is like this: Min[i]=Math.Min(A[i],Max[i-1]* A[i], Min[i-1]*A[i]), similarly Max[i]= Math.max(A[i],Max[i-1]* A[i], Min[i-1]*A[i]);

   public int maxProduct(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int localMin=A[0];  
    int localMax=A[0];  
    int globalMax=A[0];  
    for(int i=1;i<A.length;i++){  
      int temp=localMax;  
      localMax=Math.max(Math.max(A[i],localMax*A[i]),localMin*A[i]);  
      localMin=Math.min(Math.min(A[i],localMin*A[i]),temp*A[i]);  
      globalMax=Math.max(globalMax,localMax);  
    }  
    return globalMax;  
   }