LeetCode152—Maximum Product Subarray

快来打我* 2022-07-15 05:06 142阅读 0赞

## 原题 ##

[原题链接][Link 1]

> Find the contiguous subarray within an array (containing at least one number) which has the largest product.
> 
> For example, given the array \[2,3,-2,4\],  
> the contiguous subarray \[2,3\] has the largest product = 6.
> 
> Subscribe to see which companies asked this question

## 分析 ##

首先想到的是最大子序列和问题，动归方程如下，dp\[i\]表示以nums\[i\]结尾的局部最优：  
dp\[i\]=max(dp\[i−1\]\+nums\[i\],nums\[i\])(1)

由于乘法不同于加法的性质（加法的效果是累计的），乘法可以出现负负得正的情况，也就是说以nums\[i\]结尾的局部最优可能是一个很小的负数乘上一个很小的负数得到。

因此，此题需要维护两个局部变量，一个表示局部最大，一个表示局部最小。

### **代码** ###

class Solution {
    
    public:
    
        int maxProduct(vector<int>& nums)
        {
                vector<int>dp_min(nums.size());
                vector<int>dp_max(nums.size());
                dp_min[0]=nums[0];
                dp_max[0]=nums[0];
                int global=nums[0];
                for(int i = 1;i<nums.size();i++)
                {
                    if(nums[i]>0)
                    {
                        dp_max[i]=max(dp_max[i-1]*nums[i],nums[i]);
                        dp_min[i]=min(dp_min[i-1]*nums[i],nums[i]);
                    }
                    else
                    {
                        dp_max[i]=max(dp_min[i-1]*nums[i],nums[i]);
                        dp_min[i]=min(dp_max[i-1]*nums[i],nums[i]);
    
                    }
    
                    global=max(global,dp_max[i]);
                }
                return global;
    
        }
    
    };

[Link 1]: https://leetcode.com/problems/maximum-product-subarray/