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;
    }
};