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.

---

思路

这题是个典型的动归问题 ，由于求的是子序列的最大乘积 ，所以要注意0和负数的情况。

动归中要保持两个量，一个是最大的正数积，一个是最小负数积（最小负数积用来保证遇到下个负数是能获得最大的正数积）。遇到0时，两个数都置为0。

Code

int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 1;
        if (nums.size() == 1) return nums[0];

        int k = nums.size();

        int pos, neg;

        pos = nums[0]>0 ? nums[0] : 0;
        neg = nums[0]<0 ? nums[0] : 0;
        int maxP = pos;

        for (int i=1; i<k; i++){
            if (nums[i]==0){
                pos = 0;
                neg = 0;
            }
            else if(nums[i]>0){
                pos = max(nums[i], nums[i]*pos);
                neg = min(0, nums[i]*neg);
            }
            else{
                int temp = pos;
                pos = max(0, nums[i]*neg);
                neg = min(nums[i], nums[i]*temp);          
            }
            maxP = maxP>pos ? maxP : pos;
        }
        return maxP;
    
    
}