leetcode：152. 乘积最大子数组

题目来源

• leetcode：152. 乘积最大子数组

题目描述

题目解析

• 对于子数组问题，其dp一般定义为：必须以nums[i]结尾的子数组…，然后对于每一个dp[i]有两种选择：
  • 仅仅选择nums[i]
  • 以nums[i]为基地，向前扩展
• 这里特殊的是：两个负数相乘可能会变得很大，负数*正数可能会变得很小。所以我们需要同时维护两个值-----最大值、最小值

class Solution {
    
    struct info{
    
        int max;
        int min;  // 两个负数相乘可能变得很大
        info(){
    
            max = INT32_MIN;
            min = INT32_MAX;
        }
    };
public:

    int maxProduct(vector<int>& nums) {
    
        int N = nums.size();
        if(N == 0){
    
            return 0;
        }
        //该子数组中至少包含一个数字
        if(N == 1){
    
            return nums[0];
        }


        std::vector<info> dp(N);          //必须以num[i]结尾的最大乘积子数组
        dp[0].min = nums[0];
        dp[0].max = nums[0];
        int ans = nums[0];
        for (int i = 1; i < N; ++i) {
    
            int p1 = nums[i];
            int p2 = nums[i] * dp[i - 1].min;  // 两个负数相乘可能变得很大
            int p3 = nums[i] * dp[i - 1].max;       // 测试用例的答案是一个 32-位 整数。 不会溢出
            dp[i].min = std::min(p1, std::min(p2, p3));
            dp[i].max = std::max(p1, std::max(p2, p3));
            ans = std::max(ans, dp[i].max);
        }
        return ans;
    }
};

上面，因为dp[i]仅仅依赖dp[i-1]，所以：

class Solution {
    
public:

    int maxProduct(vector<int>& nums) {
    
        int N = nums.size();
        if(N == 0){
    
            return 0;
        }

        int pMin  = nums[0];
        int pMax = nums[0];
        int ans = nums[0];
        for (int i = 1; i < N; ++i) {
    
            int cMin = std::min(nums[i], std::min(nums[i] * pMin, nums[i] * pMax));
            int cMax = std::max(nums[i], std::max(nums[i] * pMin, nums[i] * pMax));
            ans = std::max(ans, cMax);
            pMin = cMin;
            pMax = cMax;
        }
        return ans;
    }
};