package coding4fun;

/**
 * Find the maximum product subarray.
 *
 * <pre>
 * Input: [-1, 2, -4, 3, -5]
 * Output: 120
 *
 * Input: [-1, 2, 3, -4]
 * Output: 24
 *
 * Input: [-3, -3]
 * Output: 9
 *
 * Input: [5, -4, 2, 3]
 * Output: 6
 *
 * Input: [1, -2, 3, -4, 5, -6]
 * Output: 360
 *
 * Input: [1, -2, -3, 0, 7, -8, -2]
 * Output: 112
 * </pre>
 */
public class Problem43 {
    private static int maxProductSubArray(int[] array) {
        int max = 1;
        int minProduct = 1;
        int maxProduct = 1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > 0) {
                minProduct = Math.min(minProduct * array[i], 1);
                maxProduct *= array[i];
            } else if (array[i] == 0) {
                minProduct = 1;
                maxProduct = 1;
            } else { // array[i] < 0
                int tmp = maxProduct;
                maxProduct = Math.max(minProduct * array[i], 1);
                minProduct = tmp * array[i];
            }
            max = Math.max(max, maxProduct);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(maxProductSubArray(new int[]{-1, 2, -4, 3, -5})); // 120
        System.out.println(maxProductSubArray(new int[]{-1, 2, 3, -4})); // 24
        System.out.println(maxProductSubArray(new int[]{-3, -3})); // 9
        System.out.println(maxProductSubArray(new int[]{5, -4, 2, 3})); // 6
        System.out.println(maxProductSubArray(new int[]{1, -2, 3, -4, 5, -6})); // 360
        System.out.println(maxProductSubArray(new int[]{1, -2, -3, 0, 7, -8, -2})); // 112
    }
}

@@ -339,178 +339,355 @@
 2%0A *
- %3C/pre%3E%0A */%0Apublic class Problem43 %7B%0A    private static int maxProductSubArray(int%5B%5D array) %7B%0A        int max = 1;%0A        int minProduct = 1;%0A        int maxProduct = 1;
+%0A * Input: %5B%5D%0A * Output: 0%0A *%0A * Input: %5B-1%5D%0A * Output: -1%0A *%0A * Input: %5B0, 1, 2, -3, -4, 0%5D%0A * Output: 24%0A * %3C/pre%3E%0A */%0Apublic class Problem43 %7B%0A    private static int maxProductSubArray(int%5B%5D array) %7B%0A        if (array.length == 0) %7B%0A            return 0;%0A        %7D%0A        int max = array%5B0%5D;%0A        int maxSoFar = array%5B0%5D;%0A        // forward
 %0A   
@@ -704,17 +704,17 @@
 int i = 
-0
+1
 ; i %3C ar
@@ -744,24 +744,35 @@
         if (
+maxSoFar * 
 array%5Bi%5D %3E 0
@@ -768,17 +768,18 @@
 rray%5Bi%5D 
-%3E
+==
  0) %7B%0A  
@@ -797,41 +797,17 @@
    m
-inProduct = Math.min(minProduct *
+axSoFar =
  arr
@@ -807,33 +807,47 @@
 r = array%5Bi%5D
-, 1)
 ;%0A   
+         %7D else %7B%0A
             
@@ -847,26 +847,27 @@
         
-maxProduct
+   maxSoFar
  *= arra
@@ -889,34 +889,71 @@
    %7D
- else if (array%5Bi%5D == 0) %7B
+%0A            max = Math.max(Math.max(maxSoFar, array%5Bi%5D), max);
 %0A   
@@ -953,32 +953,34 @@
 x);%0A        
+%7D%0A
         
 minProduct =
@@ -971,181 +971,188 @@
     
-minProduct = 1;%0A                maxProduct = 1;%0A            %7D else %7B // array%5Bi%5D %3C 0%0A                int tmp = maxProduct;%0A                maxProduct = Math.max(minProduct *
+// backward%0A        maxSoFar = array%5Barray.length - 1%5D;%0A        for (int i = array.length - 2; i %3E= 0; i--) %7B%0A            if (maxSoFar * array%5Bi%5D == 0) %7B%0A                maxSoFar =
  arr
@@ -1160,22 +1160,22 @@
 y%5Bi%5D
-, 1);%0A
+;%0A    
         
     
@@ -1174,34 +1174,44 @@
     
-        minProduct = tmp
+%7D else %7B%0A                maxSoFar
  *
+=
  arr
@@ -1262,23 +1262,41 @@
 max(
-max, maxProduct
+Math.max(maxSoFar, array%5Bi%5D), max
 );%0A 
@@ -1866,16 +1866,236 @@
  // 112%0A
+        System.out.println(maxProductSubArray(new int%5B%5D%7B%7D)); // 0%0A        System.out.println(maxProductSubArray(new int%5B%5D%7B-1%7D)); // -1%0A        System.out.println(maxProductSubArray(new int%5B%5D%7B0, 1, 2, -3, -4, 0%7D)); // 24%0A
     %7D%0A%7D%0A

Update problem 43