题目描述（中等难度）

找一个连续的子数组，使得连乘起来最大。

解法一 动态规划

开始没有往这方面想，直接想到了解法二，一会儿讲。看到 这里-time-complexity)，才想起来直接用动态规划解就可以，和 子数组最大的和思路差不多。

我们先定义一个数组 ，用 dpMax[i] 表示以第 i 个元素的结尾的子数组，乘积最大的值，也就是这个数组必须包含第 i 个元素。

那么 dpMax[i] 的话有几种取值。

  • 当 nums[i] >= 0 并且dpMax[i-1] > 0，dpMax[i] = dpMax[i-1] * nums[i]
  • 当 nums[i] >= 0 并且dpMax[i-1] < 0，此时如果和前边的数累乘的话，会变成负数，所以dpMax[i] = nums[i]
  • 当 nums[i] < 0，此时如果前边累乘结果是一个很大的负数，和当前负数累乘的话就会变成一个更大的数。所以我们还需要一个数组 dpMin 来记录以第 i 个元素的结尾的子数组，乘积最小的值。
    • 当dpMin[i-1] < 0，dpMax[i] = dpMin[i-1] * nums[i]
    • 当dpMin[i-1] >= 0，dpMax[i] = nums[i]

当然，上边引入了 dpMin 数组，怎么求 dpMin 其实和上边求 dpMax 的过程其实是一样的。

按上边的分析，我们就需要加很多的 if else来判断不同的情况，这里可以用个技巧。

我们注意到上边dpMax[i] 的取值无非就是三种，dpMax[i-1] * nums[i]、dpMin[i-1] * nums[i] 以及 。

所以我们更新的时候，无需去区分当前是哪种情况，只需要从三个取值中选一个最大的即可。

求 dpMin[i] 同理。

  1. dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);

更新过程中，我们可以用一个变量 max 去保存当前得到的最大值。

当然，动态规划的老问题，我们注意到更新 dp[i] 的时候，我们只用到 dp[i-1] 的信息，再之前的信息就用不到了。所以我们完全不需要一个数组，只需要一个变量去重复覆盖更新即可。

  1. public int maxProduct(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     int dpMax = nums[0];
  7.     int max = nums[0];
  8.     for (int i = 1; i < n; i++) {
  9.         //更新 dpMin 的时候需要 dpMax 之前的信息，所以先保存起来
  10.         int preMax = dpMax;
  11.         dpMax = Math.max(dpMin * nums[i], Math.max(dpMax * nums[i], nums[i]));
  12.         dpMin = Math.min(dpMin * nums[i], Math.min(preMax * nums[i], nums[i]));
  13.         max = Math.max(max, dpMax);
  14.     }
  15.     return max;
  16. }

解法二

如果给定的数组全部都是正数，那么子数组最大的乘积是多少呢？很简单，把所有的数字相乘即可。

但如果给定的数组存在负数呢，似乎这就变得麻烦些了。

我们继续简化问题，如果出现了偶数个负数呢？此时最大乘积又变成了，把所有的数字相乘即可。

所以，其实我们需要解决的问题就是，当出现奇数个负数的时候该怎么办。

乘积理论上乘的数越多越好，但前提是必须保证负数是偶数个。

那么对于一个有奇数个负数的数组，基于上边的原则，最大数的取值情况就是两种。

第一种，如下图，不包含最后一个负数的子数组。

第二种，如下图，不包含第一个负数的子数组。

152. Maximum Product Subarray - 图1

综上所述，最大值要么是全部数字相乘，要么是上边的两种情况。

事实上，和解法一一样，我们只要保证计算过程中包含了上边讨论的三种情况即可。

对于负数是奇数个的情况，我们采用正着遍历，倒着遍历的技巧即可。

  1. public int maxProduct(int[] nums) {
  2.     if (nums.length == 0) {
  4.     }
  5.     int max = 1;
  6.     //包含了所有数相乘的情况
  7.     //奇数个负数的情况一
  8.     for (int i = 0; i < nums.length; i++) {
  9.         max *= nums[i];
  10.         res = Math.max(res, max);
  11.     }
  12.     max = 1;
  13.     //奇数个负数的情况二
  14.     for (int i = nums.length - 1; i >= 0; i--) {
  15.         max *= nums[i];
  16.         res = Math.max(res, max);
  17.     }
  19.     return res;
  20. }

不过代码还没有结束，我们只考虑了负数和正数，没有考虑 0。如果有 0 存在的话，会使得上边的代码到 0 的位置之后 max 就一直变成 0 了。

修正这个问题可以用一个直接的方式，把数组看成下边的样子。

把数组看成几个都不含有 0 的子数组进行解决即可。

代码中，我们只需要在遇到零的时候，把 再初始化为 1 即可。

总

解法二其实是对问题本质的深挖，正常情况下，我们其实用动态规划的思想去直接求解即可。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^