152. Maximum Product Subarray

problem description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

algorithm thought

典型的动态规划问题，可以这么入手去思考状态转移，如果现在得到结果为res，新来一个数字，如果是正数，那么新的res变为res*newnum。但是如果来的是一个负数，就不好解决了，所以我们不仅要保存最大值（也就是结果），还要保存一个最小值，负数乘一个最小的负数也是有可能得到最大值的。

code

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

algorithm analysis

一次循环遍历数组，时间复杂度O(n)