LeetCode 152 Maximum Product Subarray

ShenduCC

发布于 2019-05-15 09:54:43

2940

发布于 2019-05-15 09:54:43

文章被收录于专栏：算法修养

题目

思路

维护两个数组，一个是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;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-05-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除

c++