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.
很显然是一个动态规划的问题，找到递归表达式就可以了，考虑到会有负负相乘的问题，所以应该维持一个最大的值以及一个最小的值，递归表达式如下所示：
1 maxLocal[i + 1] = max(max(maxLocal[i] * nums[i + 1], minLocal[i] * nums[i + 1]), nums[i + 1]); 2 minLocal[i + 1] = min(min(maxLocal[i] * nums[i + 1], minLocal[i] * nums[i + 1]), nums[i + 1]); 3 maxGlobal[i + 1] = max(maxGlobal[i], maxLocal[i + 1]);
代码如下所示：
1 class Solution { 2 public: 3 int maxProduct(vector<int>& nums) { 4 int sz = nums.size(); 5 if (sz == 0)return 0; 6 if (sz == 1)return nums[0]; 7 int maxP, minP, a, b, ret; 8 ret = maxP = minP = a = b = nums[0]; 9 for (int i = 1; i < sz; ++i){ 10 a = max(maxP * nums[i], minP * nums[i]); 11 b = min(maxP * nums[i], minP * nums[i]); 12 maxP = max(a, nums[i]); 13 minP = min(b, nums[i]); 14 ret = max(maxP, ret); 15 } 16 return ret; 17 } 18 19 };
LeetCode OJ：Maximum Product Subarray（子数组最大乘积）
原文：http://www.cnblogs.com/-wang-cheng/p/4887258.html