LeetCode 152. 乘积最大子数组

152. 乘积最大子数组

题目描述

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

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

示例 2:

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

解题思路

思路一： 动态规划

求数组中子区间的最大乘积，对于乘法，我们需要注意，负数乘以负数，会变成正数，所以解这题的时候我们需要维护两个变量，当前的最大值，以及最小值
1. 状态定义
定义maxDp[i]表示以第 i 个元素结尾的乘积最大子数组的乘积；
定义minDp[i]表示以第 i 个元素结尾的乘积最小子数组的乘积；

2. 转移方程
遍历数组时计算当前最大/小值，不断更新;
可以考虑把 nums[i] 加入第 i - 1 个元素结尾的乘积最大或最小的子数组的乘积中，然后和 nums[i] 这三者取最大值， 就是 第 i 个元素结尾的乘积最大子数组的乘积；
最小子数组的乘积也是一样。
转移方程如下：
maxDp[i] = max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i], nums[i]);
minDp[i] = max(minDp[i - 1] * nums[i], maxDp[i - 1] * nums[i], nums[i]);

3. 初始状态
maxDp[0] = nums[0];
minDp[0] = nums[0];

4. 返回值
返回maxDp 中最大值

实现代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let len = nums.length;
    if (len == 1) {
        return nums[0];
    }
    let maxDp = Array(len).fill(0), 
        minDp = Array(len).fill(0),
        result = nums[0];
    maxDp[0] = nums[0];
    minDp[0] = nums[0];

    for (let i = 1; i < len; i++) {
        let num = nums[i];
        maxDp[i] = Math.max(maxDp[i - 1] * num, minDp[i - 1] * num, num);
        minDp[i] = Math.min(minDp[i - 1] * num, maxDp[i - 1] * num, num);
    }
    for (let i = 1; i < len; ++i) {
        result = Math.max(result, maxDp[i]);
    }
    return result;

}; 
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

• 时间复杂度： O(n)， n是nums数组长度
• 空间复杂度： O(n)

空间复杂度优化版
由于第 i 个状态只和第 i−1 个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护 i - 1 时刻的状态，一个维护 maxDp，一个维护 minDp
优化代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let len = nums.length;
    if (len == 1) {
        return nums[0];
    }
    let maxF = nums[0],
        minF = nums[0],
        result = nums[0];

    for (let i = 1; i < len; i++) {
        let mx = maxF, mn = minF, num = nums[i]; 
        maxF = Math.max(mx * num, Math.max(num, mn * num));
        minF = Math.min(mn * num, Math.min(num, mx * num));
        result = Math.max(maxF, result);
    } 
    return result;

};  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

优化后只使用常数个临时变量作为辅助空间，与 n 无关，故空间复杂度为 O(1)

参考资料

乘积最大子数组 - 乘积最大子数组 - 力扣（LeetCode）