一起刷leetcode(152): Maximum Product Subarray


*求有最大乘积的子数组中的乘积
*
*和求最大和的原理一样都是动态规划,不一样在于求和的时候遇到负值就是减小,不需要做特殊处理
*但是在求积的时候遇到负值,积会变小但是再遇到一个负值时又会变大。
*
*所以我们在维护一个最大积的时候还需要维护一个最小积,因为最小积可能会变成最大积
*
class Solution {
public:
    int maxProduct(vector<int>& nums) {
    int i,k,input=nums[0],ma=nums[0],mi=nums[0],temp;
    k=nums.size();
    for(i=1;i<k;++i)
    {
        temp=ma;
        ma=max(max(ma*nums[i],nums[i]),mi*nums[i]);
        mi=min(min(temp*nums[i],nums[i]),mi*nums[i]);
        input=max(input,ma);
    }
    return input;
    }
};
已邀请:

PolorGhost

赞同来自:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        
       int MAX = nums[0], MIN = nums[0], curMax = nums[0], curMin = nums[0];
        
       for (int i = 1; i < nums.size(); ++i){
           int a = max(max(curMax * nums[i], curMin * nums[i]), nums[i]);
           int b = min(min(curMax * nums[i], curMin * nums[i]), nums[i]);
           curMax = a;
           curMin = b;
           MAX = max(a, MAX);
       }
        
        return MAX;
    }
};

要回复问题请先登录注册

返回顶部