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.
思路：
动态规划
整体的最优解等于遍历所有的局部最优解中的最优解
动态规划方程：
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]), min_local * A[i])
min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]), min_local * A[i])
我的代码：
public class Solution { public int maxProduct(int[] A) { if(A == null || A.length == 0) return 0; int n = A.length; int max = A[0]; int[] maxLocal = new int[n]; int[] minLocal = new int[n]; maxLocal[0] = A[0]; minLocal[0] = A[0]; for(int i = 1; i < n; i++) { int localMax = maxLocal[i-1]; maxLocal[i] = Math.max(Math.max(A[i],maxLocal[i-1]*A[i]),A[i]*minLocal[i-1]); minLocal[i] = Math.min(Math.min(A[i],minLocal[i-1]*A[i]),A[i]*localMax); max = Math.max(max,maxLocal[i]); } return max; } }
public class Solution { public int maxSubArray(int[] A) { if(A == null || A.length == 0) return 0; int n = A.length; int[] localMax = new int[n]; localMax[0] = A[0]; int max = A[0]; for(int i = 1; i < n; i++) { localMax[i] = Math.max(localMax[i-1]+A[i],A[i]); max = Math.max(max,localMax[i]); } return max; } }
原文：http://www.cnblogs.com/sunshisonghit/p/4355203.html
