Maximum Product Subarray

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.

这道题A了很久也没A出来，看了http://blog.csdn.net/salutlu/article/details/39560795做出来了

思路DP

max只可能来自三种情况

1.max * A[i] // A[i] > 0

2.min * A[i] //A[i] < 0

3.A[i]

当然min也只可能来自这三种情况

 1 public class Solution {
 2     public int maxProduct(int[] A) {
 3         if(A.length == 0)
 4             return 0;
 5         if(1 == A.length)
 6             return A[0];
 7         int curMin = A[0];
 8         int curMax = A[0];
 9         int ret = A[0];
10         
11         for(int i = 1; i < A.length; i++){
12             int temp = curMin * A[i];
13             
14             curMin = Math.min(A[i], Math.min(temp, curMax * A[i]));
15             curMax = Math.max(A[i], Math.max(temp, curMax * A[i]));
16             
17             ret = ret > curMax ? ret:curMax;
18         }
19         return ret;
20     }
21 }