首页 > 编程语言(其他) > leetcode No152. Maximum Product Subarray

leetcode No152. Maximum Product Subarray

2017年1月11日 发表评论 阅读评论

Question

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
求最大连续子数组乘积

Algorithm

与最大连续子数组和类似,乘积有一点变化要考虑到一种特殊情况:
负数和负数相乘:如果前面得到一个较小的负数,和后面一个较大的负数相乘,得到的反而是一个较大的数。
所以,我们在处理乘法的时候,除了需要维护一个局部最大值,同时还要维护一个局部最小值

Accepted Code

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0];
        int subMax=nums[0],subMin=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            int temp=subMax;
            subMax=max(max(subMax*nums[i],subMin*nums[i]),nums[i]);
            subMin=min(min(temp*nums[i],subMin*nums[i]),nums[i]);
            res=max(res,subMax);
        }
        return res;
    }
};
作者:u011391629 发表于2017/1/11 10:49:27 原文链接
阅读:181 评论:0 查看评论
分类: 编程语言(其他) 标签: