程序员人生 网站导航

leetcode No152. Maximum Product Subarray

栏目:php教程时间:2017-02-08 08:18:18

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,⑵,4],
the contiguous subarray [2,3] has the largest product = 6.
求最大连续子数组乘积

Algorithm

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

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;
    }
};

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐