LeetCode 152 Maximum Product Subarray

佚名 6年前 (2019-05-10) 随笔 724人围观抢沙发百度已收录

思路

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

维护两个数组，一个是a[i] 表示以i为结尾的子序列乘积的最大值

一个是b[i] 表示以i为结尾的子序列乘积的最小值

然后就是动态规划的思想。

c++

class Solution {
public:
    int s[1000005];
    int a[1000005];
    int b[1000005];
    int maxProduct(vector<int>& nums) {
 
    
        a[0]=nums[0];
        b[0]=nums[0];
        int m=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            a[i]=max(nums[i],max(nums[i]*a[i-1],nums[i]*b[i-1]));
            b[i]=min(nums[i],min(nums[i]*a[i-1],nums[i]*b[i-1]));
            
            m=max(m,max(a[i],max(nums[i],b[i])));
                     
            
        }
       
        return m;
    }
};