leetCode-1-0152-maximum-product-subarray.md

乘积最大子序列（中等）

题目描述

题目地址

https://leetcode-cn.com/problems/maximum-product-subarray/

解法：动态规划

• 类似题型:53. 最大子序和-解法二
• 如53题求和

    /**
    * @param {number[]} nums
    * @return {number}
    */
    var maxSubArray = function(nums) {
        var max = nums[0];
        var dp = new Array(nums.length);
        dp[0] = max;
        for(var i = 1;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    };

• 此题换成了求积
  • 求和
    • 和特点
      • 加正数和越来越大，加负数和越来越小
    • 遇到前面序列和为负数时，不加重置为新的子序列起点为当前节点
    • 或者为正数时，加上当前节点
      • 因为当前节点也有正负之分
      • 所动态转移方程为dpMax[i] = Max(dp[i-1]+nums[i],nums[i])
  • 求积
    • 子序列必须连续
    • 当前值为负数时，要想乘积最大，则必须乘以前n-1个连续子序列中的最小值
      • 乘以正数，正数越大，积会越来越小，不合题意
    • 因此本题要多维护一个dpMIn数组，用以表示前n-1个连续子序列中的最小值
    • dpMax[i-1] > 0
      • nums[i] > 0
        • dpMax[i] = dpMax[i-1] * nums[i]
      • nums[i] <= 0
        • dpMax[i] = dpMin[i-1] * nums[i]
        • dpMin[i] = nums[i]
    • dpMax[i-1] <= 0
      • nums[i] > 0
        • dpMax[i] = nums[i]
        • dpMin[i] = dpMax[i-1] * nums[i]
      • nums[i] <= 0
        • dpMax[i] = dpMin[i-1] * nums[i]
        • dpMin[i] = nums[i]
    • 因此可以直接省去以上应用于代码中的if/else判断
    • dpMax[i] = Max(dpMax[i-1] * nums[i],dpMin[i-1] * nums[i],nums[i])
    • dpMin[i] = Max(dpMax[i-1] * nums[i],dpMin[i-1] * nums[i],nums[i])

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    var n = nums.length;
    var dpMax = new Array(n);
    var dpMin = new Array(n);
    dpMax[0] = nums[0];
    dpMin[0] = nums[0];
    var max = dpMax[0];
    for(var i = 1;i<nums.length;i++){
        dpMax[i] = Math.max(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i],nums[i]);
        dpMin[i] = Math.min(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i],nums[i]);
        max = Math.max(max,dpMax[i]);
    }
    return max;
};

• 优化版++
  • 降维
  • 每次求dpMax[i]和dpMin[i]时，只与上一个dpMax[i-1]和dpMin[i-1]有关
  • 因此只需维护一个前面子序列的最大值和最小值两个变量即可，然后再乘以当前值，与前一个Max做比较即可

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    var prevMax = 1;
    var prevMin = 1;
    var max = Number.MIN_SAFE_INTEGER;
    for(var i = 0;i<nums.length;i++){
        if(nums[i] < 0){
            var tmp = prevMax;
            prevMax = prevMin;
            prevMin = tmp;
        }
        prevMax = Math.max(prevMax*nums[i],nums[i]);
        prevMin  = Math.min(prevMin*nums[i],nums[i]);
        max = Math.max(max,prevMax);
    }
    return max;
};