乘积最大子数组-中等

难度：中等

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

示例：

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

1
2
3

解题思路：

暴力解法 ```javascript var maxProduct = function(nums) { if(nums.length < 2) return nums[0] let max = -Infinity for(let i = 0; i < nums.length; i++){ let total = nums[i] max = Math.max(max, total) for(let j = i + 1; j < nums.length; j++){ total *= nums[j] max = Math.max(max, total) } } return max };


<br />动态规划：
```javascript
var maxProduct = function(nums) {
  let max = nums[0]
  let imax = 1
  let imin = 1
  for(let num of nums) {
    if(num < 0) {
      [imax, imin] = [imin, imax]
    }
    imax = Math.max(num, num * imax)
    imin = Math.min(num, num * imin)
    max = Math.max(imax, max)
  }
  return max
};

/**
  如: nums = [2,3,-2,4]
  循环

  i
  0    num = 2; imax = 2, imin = 1, max = 2
  1    num = 3  imax = 6, imin = 1, max = 6
  2    num = -2 < 0, 交换 => imax = 1, imin = 6 => imax = -2, imin = -12, max = 6
  3    num = 4  imax = 4, imin = -48, max = 6

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

← 完全平方数-中等打家劫舍 III-中等 →

# 乘积最大子数组-中等

乘积最大子数组-中等