题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

题解

我们这道题采用动态规划实现，我们利用一个二维数组dp记录当前位置之前的最大和最小乘积。具体来说，dp[i][0]表示以第i个数结尾的最小乘积，dp[i][1]表示以第i个数结尾的最大乘积，接下来讲解下实现思路，我们先声明一个 maxProduct 函数，然后函数中接受一个nums参数，然后在声明一个dp常量，值为nums参数长度的空值数组，然后使用循环，将当前dp常量中的每个值都变为二维数组默认值为[0,0]，然后将dp[0][0]和dp[0][1]都赋值为数组的第一个元素nums[0]，并将max也初始化为nums[0]，然后，从数组的第二个元素开始循环，更新dp[i][0]和dp[i][1]。具体来说，dp[i][0]的值可以从以下三个来源中选出最小值：当前数nums[i]，上一个数的最小乘积dp[i-1][0]*nums[i]，上一个数的最大乘积dp[i-1][1]*nums[i]。同理，dp[i][1]的值可以从以上三个来源中选出最大值，每次更新完dp[i][0]和dp[i][1]之后，将max更新为以下三个值的最大值：上一个数的最小乘积dp[i-1][0]*nums[i]，上一个数的最大乘积dp[i-1][1]*nums[i]，当前数nums[i]。这是因为最大乘积可能包含当前数，也可能不包含，所以需要比较三种情况，最后，函数返回max即为所求。

var maxProduct = function (nums) {
  const dp = new Array(nums.length).fill(null);
  for (let i = 0; i < dp.length; ++i) {
    dp[i] = [0, 0];
  }
  dp[0][0] = nums[0];
  dp[0][1] = nums[0];
  let max = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    dp[i][0] = Math.min(nums[i], dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]);
    dp[i][1] = Math.max(nums[i], dp[i - 1][1] * nums[i], dp[i - 1][0] * nums[i]);
    max = Math.max(max, dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i])
  }
  return max;
};