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.
解题思路：乘法与加法最大差别在于，当前元素的符号具有全局性的作用。
如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。
同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。
因此使用动态规划的方法：
记maxPro_last/minPro_last为连乘到上个元素的最大/小乘积
记maxPro_cur/minPro_cur为连乘到当前元素的最大/小乘积
记maxPro_all/minPro_all为截至（可不包括）当前元素的最大/小乘积
简化起见可以忽略对当前元素正负性分析，把当前元素与maxPro_last/minPro_last的乘积都作为产生maxPro_cur/minPro_cur的情况
class Solution { public: int maxProduct(int A[], int n) { if(n == 0) return 0; //到当前元素为止，最大/小乘积 int maxPro_all = A[0]; //以前一个元素为连乘末元素的最大/小乘积 int maxPro_last = A[0]; int minPro_last = A[0]; //以当前元素为连乘末元素的最大/小乘积 int maxPro_cur = A[0]; int minPro_cur = A[0]; for(int i = 1; i < n; i ++) { maxPro_cur = max(A[i], max(maxPro_last*A[i], minPro_last*A[i])); minPro_cur = min(A[i], min(maxPro_last*A[i], minPro_last*A[i])); maxPro_all = max(maxPro_cur, maxPro_all); maxPro_last = maxPro_cur; minPro_last = minPro_cur; } return maxPro_all; } };
【LeetCode】Maximum Product Subarray
原文：http://www.cnblogs.com/ganganloveu/p/4089925.html