首页 > 代码库 > leetcode152

leetcode152

2024-09-15 19:36:44   216人阅读

这个题的题意是求出一个数组中的最大连续子段积，一下就能想到最大连续子段和，那么也是通过计算出以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


联系
我们