Question

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,⑵,4],
the contiguous subarray [2,3] has the largest product = 6.
求最大连续子数组乘积

Algorithm

与最大连续子数组和类似，乘积有1点变化要斟酌到1种特殊情况：
负数和负数相乘：如果前面得到1个较小的负数，和后面1个较大的负数相乘，得到的反而是1个较大的数。
所以，我们在处理乘法的时候，除需要保护1个局部最大值，同时还要保护1个局部最小值。

Accepted Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0];
        int subMax=nums[0],subMin=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            int temp=subMax;
            subMax=max(max(subMax*nums[i],subMin*nums[i]),nums[i]);
            subMin=min(min(temp*nums[i],subMin*nums[i]),nums[i]);
            res=max(res,subMax);
        }
        return res;
    }
};