152.乘积最大子数组

152. 乘积最大子数组

难度中等505

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

我们可以根据正负性进行分类讨论。
考虑当前位置如果是一个负数的话， 那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负
负得正，組我们希望这个积尽可能[ 负得更多，即尽可能小。如果当前位置是一个正数的话,我们更希望以
它前一个位置结尾的某个段的积也是个正数,粗希望它尽可能地大。于是这里我们可以再维护-一个fmin(i), 它
表示以第i个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程:

它代表第i个元素结尾的乘积最大子数组的乘积fmax(i),可以考虑把a;加入第i - 1个元素结尾的乘积最大或
最小的子数组的乘积中，二者加上a;,三者取大,就是第i个元素结尾的乘积最大子数组的乘积。第i个元素结
尾的乘积最小子数组的乘积fmin(i)同理。
不难给出这样的实现:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n  = nums.size();
        int dp[n+5];
        int ret = nums[0];
        int minn = nums[0],maxx = nums[0];
        for(int i = 1;i<n;i++){
            int ma = maxx;
            int mm = minn;
            maxx = max(maxx*nums[i],max(nums[i],nums[i]*mm));
            minn = min(minn*nums[i],min(nums[i],nums[i]*ma));

            ret = max(ret,maxx);
        }
        return ret;
    }
};