LeetCode-152-Maximum Product Subarray

算法描述:

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解题思路:用动态规划求解。最小值(最大值)分三种情况:当前值,当前值乘以前一个最小值(最大值),以及当前值乘以前一个最大值(最小值)。递推式为:

minVale[i] = min(min(nums[i],nums[i]*maxValue[i-1]),nums[i]*minValue[i-1]);

maxVale[i] = max(max(nums[i],nums[i]*maxValue[i-1]),nums[i]*minValue[i-1]);

内存空间还可以压缩。

    int maxProduct(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> minVal(nums.size(),0);
        vector<int> maxVal(nums.size(),0);
        
        minVal[0] = min(nums[0],0);
        maxVal[0] = max(nums[0],0);
        
        int res = maxVal[0];
        
        for(int i=1; i < nums.size(); i++){
            minVal[i] = min(min(nums[i], nums[i]*maxVal[i-1]),minVal[i-1]*nums[i]);
            maxVal[i] = max(max(nums[i], nums[i]*minVal[i-1]),maxVal[i-1]*nums[i]);
            if(res < maxVal[i])
                res = maxVal[i];
        }
        return res;
    }

 

上一篇:扑克牌中的顺子


下一篇:创建指定个数,指定最小值,最大值的随机数