package com.interview.array;

/**
 * Date 12/31/2015
 * @author Tushar Roy
 *
 * Given an array of postive and negative numbers find max product subarray.
 *
 * Time complexity is O(n)
 * Space complexity is O(1)
 *
 * http://www.geeksforgeeks.org/maximum-product-subarray/
 */
public class MaxProductSubarray {

    public int maxProduct(int input[]){
        int maxEnding = 1;
        int minEnding = 1;
        int maxSoFar = 1;
        for (int i = 0; i < input.length; i++) {
            if (input[i] > 0) {
                maxEnding = maxEnding*input[i];
                minEnding = Math.min(minEnding*input[i], 1);
            } else if (input[i] == 0) {
                maxEnding = 1;
                minEnding = 1;
            } else {
                int t = maxEnding;
                maxEnding = Math.max(minEnding*input[i], 1);
                minEnding = t * input[i];
            }

            if (maxSoFar < maxEnding) {
                maxSoFar = maxEnding;
            }
        }
        return maxSoFar;
    }
    
    public static void main(String args[]){
        MaxProductSubarray mps = new MaxProductSubarray();
        int input[] = {-6,-3,8,-9,-1,-1,3,6,9,0,3,-1};
        System.out.println(mps.maxProduct(input));
    }
}

@@ -39,18 +39,18 @@
 ate 
-12/31
+04/%607
 /201
-5
+6
 %0A * 
@@ -78,80 +78,115 @@
 %0A * 
-Given an array of postive and negative numbers find max product subarray
+Find the contiguous subarray within an array (containing at least one number) which has the largest product
 .%0A *
@@ -302,16 +302,75 @@
 barray/%0A
+ * https://leetcode.com/problems/maximum-product-subarray/%0A
  */%0Apubl
@@ -433,17 +433,17 @@
 (int
- input%5B%5D)
+%5B%5D nums) 
 %7B%0A  
@@ -453,24 +453,18 @@
    int m
-axEnd
 in
-g
  = 1;%0A  
@@ -474,24 +474,18 @@
    int m
-inEnding
+ax
  = 1;%0A  
@@ -505,17 +505,23 @@
 SoFar = 
-1
+nums%5B0%5D
 ;%0A      
@@ -542,21 +542,20 @@
  0; i %3C 
-input
+nums
 .length;
@@ -574,29 +574,28 @@
         if (
-input
+nums
 %5Bi%5D %3E 0) %7B%0A 
@@ -616,32 +616,21 @@
  max
-Ending = maxEnding*input
+ = max * nums
 %5Bi%5D;
@@ -649,22 +649,16 @@
      min
-Ending
  = Math.
@@ -664,34 +664,81 @@
 .min(min
-Ending*input%5Bi%5D, 1
+ * nums%5Bi%5D, 1);%0A                maxSoFar = Math.max(maxSoFar, max
 );%0A     
@@ -755,21 +755,20 @@
 lse if (
-input
+nums
 %5Bi%5D == 0
@@ -788,24 +788,18 @@
        m
-axEnd
 in
-g
  = 1;%0A  
@@ -817,22 +817,66 @@
    m
-inEnding
+ax
  = 1;%0A
+                maxSoFar = Math.max(maxSoFar, 0);%0A
     
@@ -915,30 +915,34 @@
  int t = max
-Ending
+ * nums%5Bi%5D
 ;%0A          
@@ -950,22 +950,21 @@
      max
-Ending
+SoFar
  = Math.
@@ -972,71 +972,31 @@
 ax(m
-inEnding*input%5Bi%5D, 1);%0A                minEnding = t * input
+axSoFar, min * nums
 %5Bi%5D
+)
 ;%0A  
@@ -1009,87 +1009,67 @@
     
-%7D%0A%0A
     
-        if (maxSoFar %3C maxEnding) %7B%0A                maxSoFar = maxEnding
+max = Math.max(1, min*nums%5Bi%5D);%0A                min = t
 ;%0A  
@@ -1259,32 +1259,43 @@
 %7B-6,
+ 
 -3,
+ 
 8,
+ 
 -9,
+ 
 -1,
+ 
 -1,
+ 
 3,
+ 
 6,
+ 
 9,
+ 
 0,
+ 
 3,
+ 
 -1%7D;

update max production subarray qs