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.
看到这道题，很明显的一套动态规划类型的题目，和最长升序子序列之类的十分类似，那么首先就是想递推公式。
思路①：
subarray[i][j]表示数组中从第 i 到第 j 位置的数字组成的子数组的乘积。因此我们有如下递推公式：
subarray[i][j] = subarray[i][j-1] * array[j]
很显然，这种做法需要一个二重循环，时间复杂度是O(n^2)
思路②：
因为考虑到，最大的一个子数组最大乘积可以分为两种情况：
A.之前的子数组乘积为负，当前的数字也为负，相乘为一个大正数
B.之前的子数组乘积为正，当前的数字也是正，相乘为一个正数
考虑到上面的两种情况，因此我们需要保存两个数组，分别记录当前的最大正整数乘积和最小负整数乘积
positive_subarray[i]:表示数组前i个数之前的最大相乘正值（包括第 i 个数）
negative_subarray[i]:表示数组前i个数之前的最大相乘负值（包括第 i 个数）
所以有：
当array[i] >= 0 时：
positive_subarray[i] = max( positive_subarray[i-1]*array[i], array[i] )
negative_subarray[i] = negative_subarray[i-1]*array[i]
当array[i] < 0 时：
positive_subarray[i] = negative_subarray[i-1]*array[i]
negative_subarray[i] = min( positive_subarray[i-1]*array[i], array[i])
这样程序的复杂度就降低到了O(n)
代码如下：
int maxProduct(vector& nums)
{
if(nums.empty())
return 0;
vector positive_subarray = vector(nums.size(),0);
vector negative_subarray = vector(nums.size(),0);
int max_product;
int len = nums.size();
if(nums[0] < 0)
negative_subarray[0] = nums[0];
else
positive_subarray[0] = nums[0];
max_product = nums[0];
for(int i=1;i
{
if(nums[i]>=0)
{
positive_subarray[i] = max(positive_subarray[i-1]*nums[i],nums[i]);
negative_subarray[i] = negative_subarray[i-1]*nums[i];
}
else
{
positive_subarray[i] = negative_subarray[i-1]*nums[i];
negative_subarray[i] = min(positive_subarray[i-1]*nums[i],nums[i]);
}
if(positive_subarray[i]>max_product)
max_product = positive_subarray[i];
}
return max_product;
}