[LeetCode] 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.

Analysis:

Similar with Maximum subarray, we need to maintain an array for the maximum product that ends at index i. To achieve that, we need to know the minimum product that ends at i, because some elements might be negative.

If num[i+1] is negative, Max[i+1] = max(Min[i]*num[i+1], num[i+1]),

else Max[i+1] = max(Max[i]*num[i+1], num[i+1]);

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