力扣152题：乘积最大子数组

力扣152题：乘积最大子数组

题目描述

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

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

子数组 是数组的连续子序列。

输入输出样例

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

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

解法一，使用动态规划方法

    //使用动态规划的方法，首先需要了解状态转移方程的转换条件
    //可以明显的看出，当存在复数的时候，状态转移条件不够用，因此需要保存当前对应的最大值和最小值
    int maxProduct(vector<int>&nums)
    {
    
        if(nums.empty())
        {
    
            return 0;
        }

        int length=nums.size();

        //建立状态转移方程，二维的状态转移方程，1代表最大值， 0代表最小值

        vector<vector<int>>dp(length,vector<int>(2));

        //初始化状态,初始的最大最小值都是本身
        dp[0][0]=nums[0];
        dp[0][1]=nums[0];

        for(int i=1;i<length;i++)
        {
    
            //当对应的值大于0时
            if(nums[i]>=0)
            {
    
                dp[i][1]=max(nums[i],dp[i-1][1]*nums[i]);
                dp[i][0]=min(nums[i],dp[i-1][0]*nums[i]);
            }

            else
            {
    
                dp[i][1]=max(nums[i],dp[i-1][0]*nums[i]);
                dp[i][0]=min(nums[i],dp[i-1][1]*nums[i]);
            }
        }

        //获得最大值
        int res=dp[0][1];

        for(int i=1;i<length;i++)
        {
    
            res=max(res,dp[i][1]);
        }
        return res;
    }

解法二，优化动态规划的空间

   //优化动态规划的空间复杂度
    int maxProduct2(vector<int>nums)
    {
    
        //保存当前的最大，最小的值

        int maxValue=nums[0];
        int minValue=nums[0];
        int res=nums[0];

        for(int i=1;i<nums.size();i++)
        {
    
            int tempMax=maxValue;
            int tempMin=minValue;

            //考虑到正负数的不同，因此设置两个值
            maxValue=max(tempMax*nums[i],max(nums[i],tempMin*nums[i]));
            minValue=min(tempMin*nums[i],min(nums[i],tempMax*nums[i]));
            //获取当前的最大值
            res=max(maxValue,res);
        }
        return res;

    }