第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0152. 乘积最大子数组

题目地址(152. 乘积最大子数组)

题目描述

1
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
2
3
4
5
示例 1:
6
7
输入: [2,3,-2,4]
8
输出: 6
9
解释: 子数组 [2,3] 有最大乘积 6。
10
示例 2:
11
12
输入: [-2,0,-1]
13
输出: 0
14
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
Copied!

前置知识

  • 滑动窗口

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续,笔者首先想到的就是滑动窗口,但是这里比较特殊,我们不能仅仅维护一个最大值,因此最小值(比如-20)乘以一个比较小的数(比如-10) 可能就会很大。 因此这种思路并不方便。
首先来暴力求解,我们使用两层循环来枚举所有可能项,这种解法的时间复杂度是 O(n^2), 代码如下:
1
var maxProduct = function (nums) {
2
let max = nums[0];
3
let temp = null;
4
for (let i = 0; i < nums.length; i++) {
5
temp = nums[i];
6
for (let j = i + 1; j < nums.length; j++) {
7
temp *= nums[j];
8
max = Math.max(temp, max);
9
}
10
}
11
12
return max;
13
};
Copied!
前面说了最小值(比如-20)乘以一个比较小的数(比如-10)可能就会很大 。因此我们需要同时记录乘积最大值和乘积最小值,然后比较元素和这两个的乘积,去不断更新最大值。当然,我们也可以选择只取当前元素。因此实际上我们的选择有三种,而如何选择就取决于哪个选择带来的价值最大(乘积最大或者最小)。
这种思路的解法由于只需要遍历一次,其时间复杂度是 O(n),代码见下方代码区。

关键点

  • 同时记录乘积最大值和乘积最小值

代码

代码支持:Python3,JavaScript, CPP
Python3 Code:
1
class Solution:
2
def maxProduct(self, nums: List[int]) -> int:
3
n = len(nums)
4
max__dp = [1] * (n + 1)
5
min_dp = [1] * (n + 1)
6
ans = float('-inf')
7
8
for i in range(1, n + 1):
9
max__dp[i] = max(max__dp[i - 1] * nums[i - 1],
10
min_dp[i - 1] * nums[i - 1], nums[i - 1])
11
min_dp[i] = min(max__dp[i - 1] * nums[i - 1],
12
min_dp[i - 1] * nums[i - 1], nums[i - 1])
13
ans = max(ans, max__dp[i])
14
return ans
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
当我们知道动态转移方程的时候,其实应该发现了。我们的 dp[i] 只和 dp[i - 1]有关,这是一个空间优化的信号,告诉我们可以借助两个额外变量记录即可
Python3 Code:
1
class Solution:
2
def maxProduct(self, nums: List[int]) -> int:
3
n = len(nums)
4
a = b = 1
5
ans = float('-inf')
6
7
for i in range(1, n + 1):
8
temp = a
9
a = max(a * nums[i - 1],
10
b * nums[i - 1], nums[i - 1])
11
b = min(temp * nums[i - 1],
12
b * nums[i - 1], nums[i - 1])
13
ans = max(ans, a)
14
return ans
Copied!
JavaScript Code:
1
var maxProduct = function (nums) {
2
let max = nums[0];
3
let min = nums[0];
4
let res = nums[0];
5
6
for (let i = 1; i < nums.length; i++) {
7
let tmp = min;
8
min = Math.min(nums[i], Math.min(max * nums[i], min * nums[i])); // 取最小
9
max = Math.max(nums[i], Math.max(max * nums[i], tmp * nums[i])); /// 取最大
10
res = Math.max(res, max);
11
}
12
return res;
13
};
Copied!
CPP Code:
1
class Solution {
2
public:
3
int maxProduct(vector<int>& A) {
4
int maxProd = 1, minProd = 1, ans = INT_MIN;
5
for (int n : A) {
6
int a = n * maxProd, b = n * minProd;
7
maxProd = max({n, a, b});
8
minProd = min({n, a, b});
9
ans = max(ans, maxProd);
10
}
11
return ans;
12
}
13
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解