首页 > 代码库 > leetcode152

leetcode152

这个题的题意是求出一个数组中的最大连续子段积,一下就能想到最大连续子段和,那么也是通过计算出以a[i]结尾的最大连续子段积,然后每次更新来求出最大值。

设dp[i],以a[i]结尾的最大连续子段积。

注意数组中存在负数,当处理负数时,如果dp[i-1]能够表示以i-1结尾的最小负数,这两者相乘就是以a[i]结尾的最大积了.因此想到应该同时维护两个dp数组,分别是以a[i]结尾的最大正数,和以a[i]为结尾的最小负数。

明白了这一点,接下来要考虑的就是初始化的问题,只需要初始化位置0即可,当a[0]>0时,dp1[0]=a[0],此时应该将dp2[0]赋为0,这样才能保证后面更新的时候的正确性,对另一种情况同理

    int maxProduct(vector<int>& nums) {
        
        int n=nums.size();
        int dp1[100005];
        int dp2[100005];
        if(n==1)
        return nums[0];
        if(nums[0]>=0)
        {
            dp1[0]=nums[0];
            dp2[0]=0;
        }
        else
        {
            dp2[0]=nums[0];
            dp1[0]=0;
        }
        int res=0;
        for(int i=1;i<n;i++)
        {
            if(nums[i]==0)
            {
                dp1[i]=0;
                dp2[i]=0;
            }
            else if(nums[i]>0)
            {
                dp1[i]=max(nums[i],dp1[i-1]*nums[i]);
                res=max(res,dp1[i]);
                dp2[i]=dp2[i-1]*nums[i];
            }
            else
            {
                dp1[i]=dp2[i-1]*nums[i];
                res=max(res,dp1[i]);
                dp2[i]=min(nums[i],dp1[i-1]*nums[i]);
            }
        }
        return max(res,dp1[0]);
    }

  

leetcode152