1. 题目描述

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

示例 1:

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

示例 2:

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

2. 解题思路

对于这道题目，我们可以使用动态规划来解答。

我们只需要在遍历数组时，不断更新最大值即可，这个过程中，我们需要维护两个值：

  • max，当前的最大值，将当前的值与当前的值和之前的最大值的乘积进行对比，保存最大值
  • min，当前的最小值，将当前的值与当前的值和之前的最小值的乘积进行对比，保存最小值

我们这里求的是最大值，那为啥还要保存最小值呢？这是因为数组中可能会有负数，当当前的值是负数时，与之前的值相乘就会导致最大值和最小值交换，所以我们需要维护一个最大值和一个最小值。然后不断使用当前的最大值保存为结果，最后返回结果即可。

复杂度分析：

  • 时间复杂度：O(n)，我们需要遍历一遍数组，所以时间复杂度为O(n)；

  • 空间复杂度：O(1)，这里我们需要的额外空间为常数级，所以空间复杂度为O(1)。

    3. 代码实现

    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var maxProduct = function(nums) {
    6.   let res = -Infinity, max = 1, min = 1;
    8.   for(let i = 0; i < nums.length; i++){
    9.       if(nums[i] < 0){
    10.           let temp = max
    11.           max = min
    12.           min = temp
    13.       }
    14.       max = Math.max(nums[i], nums[i] * max)
    15.       min = Math.min(nums[i], nums[i] * min)
    17.       res = Math.max(res, max)
    18.   }
    19.   return res
    20. };

    4. 提交结果

    image.png