求最大乘积连续子数组

这个题目其实还是很恶心人的，很多测试用例都贼恶心

1.状态表达式:

那么遇到eg：1 2 3 4 5 像这种连续的正数可以很顺利的通过
但是遇到eg：[-2,3,-4] 取最大值就只能取到3，可是最大值应该是 -2 * 3 *-4 才对
所以一个dp表只用来存最大值是不够的，还应该设置一个_dp表专门来存最小值（小于0）
就可以让dp取最大的空间变大dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));

2.状态转移方程就是：

dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));
_dp[i]=min(dp[i-1]*nums[i-1],min(_dp[i-1]*nums[i-1],nums[i-1]));

3.初始化：

dp[0]一定要初始化为1，否则后面的所有值都是0，不能影响dp表后面的值

dp[0]=1,_dp[0]=1;

4.填表顺序：

从左往右

5.返回值：

返回最大的dp值，因为dp[i]表示:以i为结尾，所有子数组最大乘积的值

代码编写：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+1);
        vector<int> _dp(n+1);
        dp[0]=1,_dp[0]=1;
        int ret=nums[0];
        for(int i=1;i<=n;i++)
        {
            dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));
            _dp[i]=min(dp[i-1]*nums[i-1],min(_dp[i-1]*nums[i-1],nums[i-1]));
            
            ret=max(dp[i],ret);
        }
        return ret;
    }
};

总结：

求关于子数组乘积，从上面可以看出，一个最大dp表是不够的，还需要一个最小的dp表来表示负数，然后来扩大最大dp表的范围