152.乘积最大子数组

链接：152.乘积最大子数组
难度：Medium
标签：数组、动态规划
简介：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

题解 1 - javascript

• 编辑时间：2020-05-18
• 执行用时：72ms
• 内存消耗：36.1MB
• 编程语言：javascript
• 解法介绍：dp[i]=以 i 结尾的最大乘积。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  const len = nums.length;
  const zeroNum = nums[0];
  if (len === 1) return zeroNum;
  const dpMax = [zeroNum];
  const dpMin = [zeroNum];
  let max = zeroNum;
  for (let i = 1; i < len; i++) {
    const num = nums[i];
    const prevMax = dpMax[i - 1] * num;
    const prevMin = dpMin[i - 1] * num;
    max = Math.max(
      max,
      (dpMax[i] = Math.max(num, prevMax, prevMin)),
      (dpMin[i] = Math.min(num, prevMax, prevMin))
    );
  }
  return max;
};

题解 2 - javascript

• 编辑时间：2020-05-18
• 执行用时：72ms
• 内存消耗：35.2MB
• 编程语言：javascript
• 解法介绍：利用取模把数组大小控制在 2 个数量。

var maxProduct = function (nums) {
  const len = nums.length;
  const zeroNum = nums[0];
  if (len === 1) return zeroNum;
  const dpMax = [zeroNum];
  const dpMin = [zeroNum];
  let max = zeroNum;
  for (let i = 1; i < len; i++) {
    const num = nums[i];
    const prevMax = dpMax[(i - 1) % 2] * num;
    const prevMin = dpMin[(i - 1) % 2] * num;
    max = Math.max(
      max,
      (dpMax[i % 2] = Math.max(num, prevMax, prevMin)),
      (dpMin[i % 2] = Math.min(num, prevMax, prevMin))
    );
  }
  return max;
};