/**
 * 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.
 * 
 * Tags: Array, DP
 */
class MaxProductSubArr {
    
    /**
     * DP, update according to A[i]
     * f(k) = Largest product subarray, from index 0 up to k.
     * g(k) = Smallest product subarray, from index 0 up to k.
     * 
     * f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
     * g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
     */
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) return 0;

        int max = A[0], min = A[0], res = A[0];
        for (int i = 1; i < A.length; i++) {
            int preMax = max, preMin = min; // results of last loop
            max = Math.max(Math.max(A[i], preMax * A[i]), preMin * A[i]);
            min = Math.min(Math.min(A[i], preMax * A[i]), preMin * A[i]);
            res = Math.max(max, res);
        }
        return res;
    }
}

@@ -1,12 +1,64 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A
 /**%0A * Find 
@@ -121,19 +121,16 @@
 east one
-%0A *
  number)
@@ -160,24 +160,27 @@
 product.%0A * 
+%3Cp%3E
 %0A * For exam
@@ -281,32 +281,179 @@
 %0A * 
-%0A * Tags: Array, DP%0A */%0A
+%3Cp%3E%0A * Company Tags: LinkedIn%0A * Tags: Array, Dynamic Programming%0A * Similar Problems: (M) Maximum Subarray, (E) House Robber, (M) Product of Array Except Self%0A */%0Apublic 
 clas
@@ -470,23 +470,21 @@
 ctSubArr
+ay
  %7B%0A
-    
 %0A    /**
@@ -497,34 +497,169 @@
 * DP
-, update according to A%5Bi%5D
+. Bottom-up.%0A     * We need to track both maximum product and minimum product.%0A     * In case a minimum product multiply by a negative number and become maximum.
 %0A   
@@ -666,18 +666,17 @@
   * f(k)
- =
+:
  Largest
@@ -727,18 +727,17 @@
   * g(k)
- =
+:
  Smalles
@@ -785,16 +785,270 @@
 %0A     * 
+Similar to max sum subarray, the max product candidates are:%0A     * 1. Build on previous subarray max product: f(k-1) * A%5Bk%5D%0A     * 2. Build on previous subarray min product: g(k-1) * A%5Bk%5D%0A     * 3. Start from right here: A%5Bk%5D%0A     * Recurrence Relation:
 %0A     * 
@@ -1148,24 +1148,102 @@
 1) * A%5Bk%5D )%0A
+     * Base:%0A     * Initialize max, min and final result as the first number.%0A
      */%0A    
@@ -1270,17 +1270,20 @@
 t(int%5B%5D 
-A
+nums
 ) %7B%0A    
@@ -1290,17 +1290,20 @@
     if (
-A
+nums
  == null
@@ -1306,17 +1306,20 @@
 null %7C%7C 
-A
+nums
 .length 
@@ -1328,17 +1328,41 @@
  0) 
-return 0;
+%7B%0A            return 0;%0A        %7D
 %0A%0A  
@@ -1377,17 +1377,20 @@
 t max = 
-A
+nums
 %5B0%5D, min
@@ -1392,17 +1392,20 @@
 , min = 
-A
+nums
 %5B0%5D, res
@@ -1407,17 +1407,20 @@
 , res = 
-A
+nums
 %5B0%5D;%0A   
@@ -1444,17 +1444,20 @@
  1; i %3C 
-A
+nums
 .length;
@@ -1515,28 +1515,49 @@
  // 
-results of last loop
+IMPORTANT: max and min need tp be stored.
 %0A   
@@ -1589,17 +1589,20 @@
 ath.max(
-A
+nums
 %5Bi%5D, pre
@@ -1599,33 +1599,36 @@
 ms%5Bi%5D, preMax * 
-A
+nums
 %5Bi%5D), preMin * A
@@ -1618,33 +1618,36 @@
 s%5Bi%5D), preMin * 
-A
+nums
 %5Bi%5D);%0A          
@@ -1672,17 +1672,20 @@
 ath.min(
-A
+nums
 %5Bi%5D, pre
@@ -1690,17 +1690,20 @@
 reMax * 
-A
+nums
 %5Bi%5D), pr
@@ -1709,17 +1709,20 @@
 reMin * 
-A
+nums
 %5Bi%5D);%0A  

update max product subarray