LeetCode 152. 乘积最大子序列

淡淡的烟草味﹌ 2023-07-03 06:06 81阅读 0赞

### 解题思路 ###

dp\[i\]表示以nums\[i\]结尾的子数组的最大乘积。  
需要讨论nums\[i\]的正负  
当nums\[i\]>0时，需要向前找到第一个非正数，假定nums\[j\]<=0 , 那么此时dp\[i\]=max(num\[i\]*…nums\[j-1\]dp\[j\],num\[i\]…nums\[j-1\]) 其中num\[i\]*…nums\[j-1\]表示连乘。

同理 nums\[i\]<0时，需要向前找到第一个非正数。状态转移方程同上  
当nums\[i\]==0时。dp\[i\]=0

直接看代码更清楚。写的时候，注意界限。

### 代码 ###

class Solution { 
    public:
        int maxProduct(vector<int>& nums) { 
            int n=nums.size();
            int dp[n+3];
            dp[0]=1;
            int M=-999999;
            for(int i=1;i<=n;i++)
            { 
                if(nums[i-1]<0)
                { 
                    int j=i-1;
                    int tmp=nums[i-1];
                    while(j>=1&&nums[j-1]>0)
                    { 
                        tmp*=nums[j-1];
                        j--;
                    }
                    if(j>=1)
                    { 
                        tmp*=nums[j-1];
                        dp[i]=max(tmp*dp[j-1],tmp);
                    }
                    else
                    { 
                        dp[i]=max(tmp,nums[i-1]);
                    }
                }
                else if(nums[i-1]>0)
                { 
                    int j=i-1;
                    int tmp=nums[i-1];
                    while(j>=1&&nums[j-1]>0)
                    { 
                        tmp*=nums[j-1];
                        j--;
                    }
                    if(j>=1)
                    { 
                        dp[i]=max(tmp*dp[j],tmp);
                    }
                    else
                    { 
                        dp[i]=tmp;
                    }
                }
                else
                { 
                    dp[i]=0;
                }
                M=max(M,dp[i]);
            }
            return M;
        }
    };