Question 152: product maximum subarray

Power button 152 topic ： Product maximum subarray

Title Description

Give you an array of integers nums , Please find the non empty continuous subarray with the largest product in the array （ The subarray contains at least one number ）, And returns the product of the subarray .

The answer to the test case is 32- position Integers .

Subarray Is a continuous subsequence of an array .

I/o sample

 Input : nums = [2,3,-2,4]
 Output : 6
 explain :  Subarray  [2,3]  There is a maximum product  6.

 Input : nums = [-2,0,-1]
 Output : 0
 explain :  The result can't be  2,  because  [-2,-1]  It's not a subarray .

Solution 1 , Using dynamic programming method

    // Using dynamic programming , First of all, we need to understand the transformation conditions of the state transition equation 
    // It's obvious , When there is a complex number , Insufficient state transition conditions , Therefore, you need to save the current corresponding maximum and minimum values 
    int maxProduct(vector<int>&nums)
    {
    
        if(nums.empty())
        {
    
            return 0;
        }

        int length=nums.size();

        // Establish the state transition equation , Two dimensional state transition equation ,1 For the maximum , 0 Represents the minimum value 

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

        // Initialization status , The initial maximum and minimum values are themselves 
        dp[0][0]=nums[0];
        dp[0][1]=nums[0];

        for(int i=1;i<length;i++)
        {
    
            // When the corresponding value is greater than 0 when 
            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]);
            }
        }

        // Get the maximum 
        int res=dp[0][1];

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

Solution 2 , Optimize the space of Dynamic Planning

   // Optimize the spatial complexity of dynamic programming 
    int maxProduct2(vector<int>nums)
    {
    
        // Save the current maximum , The minimum value 

        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;

            // Considering the difference between positive and negative numbers , So set two values 
            maxValue=max(tempMax*nums[i],max(nums[i],tempMin*nums[i]));
            minValue=min(tempMin*nums[i],min(nums[i],tempMax*nums[i]));
            // Get the current maximum 
            res=max(maxValue,res);
        }
        return res;

    }