题目

题目来源：力扣（LeetCode）

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

示例 1:

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

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路分析

  • 计算子数组乘积公式：dp[n] = Math.max(dp[n-1] * val[n], val[n])
  • 遍历数组时计算当前最大值，不断更新
  • 令imax为当前最大值，则当前最大值为 max_num = max(max_num * nums[i], nums[i])
  • 由于存在负数，那么最大值乘以最小值变成最小值，最小值乘以负数就是最大。因此还需要维护当前最小值min_num，min_num = min(min_num * nums[i], nums[i])
  • 当负数出现时则imax与imin进行交换再进行下一步计算
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maxProduct = function (nums) {
  6.   // ans:当前找到的连续子数组的最大值，
  7.   // max_num：前一个最大值，
  8.   // min_num：前一个最小值，
  9.   // 因为是乘法关系，所以初始化为1
  10.   let ans = -Infinity, max_num = 1, min_num = 1;
  11.   for (const x of nums) {
  12.     // 大小关系发生颠倒
  13.     // 如果 x 是负数，由于乘积关系：
  14.         // 最大值乘以负数变成了最小值；
  15.         // 最小值乘以同一个负数变成最大值；
  16.     if (x < 0) {
  17.       let temp;
  18.       temp = max_num;
  19.       max_num = min_num;
  20.       min_num = temp;
  21.     }
  22.     max_num = Math.max(x * max_num, x);
  23.     min_num = Math.min(x * min_num, x);
  24.     ans = Math.max(ans, max_num);
  25.   }
  26.   return ans;
  27. };

参考阅读： https://leetcode-cn.com/problems/maximum-product-subarray/solution/dong-tai-gui-hua-li-jie-wu-hou-xiao-xing-by-liweiw/ https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/