python code for max product subarray

Tushar Roy · Tushar Roy · commit a55ecfba110c · 2015-12-31T16:45:25.000-06:00
diff --git a/python/array/maxproductsubarray.py b/python/array/maxproductsubarray.py
@@ -0,0 +1,24 @@
+#  http://www.geeksforgeeks.org/maximum-product-subarray/
+
+def max_product(input):
+    max_ending = 1
+    min_ending = 1
+    max_so_far = 1
+    for i in input:
+        if i > 0:
+            max_ending = max_ending * i
+            min_ending = min(min_ending*i, 1)
+        elif i == 0:
+            max_ending = 1
+            min_ending = 1
+        else:
+            t = max_ending
+            max_ending = max(min_ending*i, 1)
+            min_ending = t * i
+        if max_so_far < max_ending:
+            max_so_far = max_ending
+    return max_so_far
+
+if __name__ == '__main__':
+    input = [-6,-3,8,-9,-1,-1,3,6,9,0,3,-1]
+    print(max_product(input))
diff --git a/src/com/interview/array/MaxProductSubarray.java b/src/com/interview/array/MaxProductSubarray.java
@@ -1,34 +1,40 @@
 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 max = -1;
-        int maxNeg = 1;
+        int maxEnding = 1;
+        int minEnding = 1;
         int maxSoFar = 1;
-        for(int i =0; i < input.length; i++){
-            if(input[i] == 0){
-                maxNeg = 1;
-                maxSoFar = 1;
-                continue;
+        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(input[i] < 0){
-                maxSoFar = 1;
-            }else{
-                maxSoFar = maxSoFar * input[i];
-            }
-            maxNeg = maxNeg*input[i];
-            if(max < maxNeg){
-                max = maxNeg;
-            }
-            if(max < maxSoFar){
-                max = maxSoFar;
+
+            if (maxSoFar < maxEnding) {
+                maxSoFar = maxEnding;
             }
         }
-        return max;
+        return maxSoFar;
     }
     
     public static void main(String args[]){
