力扣题解（乘积最大子数组）

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组

（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

本题思路是分两个数组分别保存前i个为正的最大值和前i个为负的最大值，然后对第i个为正，负分情况讨论。当第i个为正时，则pos[i]=pos[i-1]*num[i],negpos[i-1]=negpos[i]*num[i].当第i个为负时，则pos[i]=negpos[i-1]*num[i],negpos[i-1]=pos[i]*num[i].为0则全化为0即可。这类题的特点是存在频繁的正负号的转换，因此需要分别对正，负数保存。

ps：本题最后一个案例过不了，官方做法也是最后一个案例过不了，貌似是乘积过大导致。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
    size_t n=nums.size();
    vector<int>maxx(n,INT_MIN);//包含i的最大值
    vector<int>minx(n,INT_MAX);

    maxx[0]=minx[0]=nums[0];
    for(int i=1;i<n;i++)
    {
        int cur=nums[i];
        if(cur>=0)
        {
            maxx[i]=max(nums[i],maxx[i-1]*cur);
            minx[i]=min(nums[i],minx[i-1]*cur);
        }
        else
        {
            maxx[i]=max(nums[i],minx[i-1]*cur);
            minx[i]=min(nums[i],maxx[i-1]*cur);
        }
    }
    int ret=nums[0];
    for(int i=1;i<n;i++)
    {
       if(maxx[i]>ret)
       {
        ret=maxx[i];
       }

    }
    return ret;

    }
};