152. 乘积最大子数组
题目描述
输入一个整数数组 nums。在所有非空的连续子数组中，找出元素乘积最大的那一个，返回这个最大乘积。
子数组必须由相邻元素构成，至少含一个元素。只含一个元素时，乘积就是该元素本身。
数据保证答案在 32 位整数范围内。
示例 1
输入：nums = [2,3,-2,4] 输出：6
解释：连续的 [2,3] 乘积为 6，是最大值。
示例 2
输入：nums = [-2,0,-1] 输出：0
解释：-2 和 -1 不相邻，不能组成子数组，所以最大乘积是 [0] 给出的 0。
数据范围
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10nums任意子数组的乘积都在 32 位整数范围内。
解题思路：动态规划（最大最小积）
同时维护以当前位置结尾的最大积和最小积，因为负数会交换两者。
为什么正确
max_prod、min_prod 分别是当前前缀中以当前位置结尾的最大和最小乘积。
复杂度分析
时间 O(n)，空间 O(1)；按索引遍历，避免 nums[1:] 的 O(n) 切片。
易错点
遇到负数必须交换最大积和最小积，否则会丢掉负负得正的机会。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
max_prod = min_prod = answer = nums[0]
for i in range(1, len(nums)):
x = nums[i]
if x < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(x, max_prod * x)
min_prod = min(x, min_prod * x)
answer = max(answer, max_prod)
return answerclass Solution {
public int maxProduct(int[] nums) {
int maxProd = nums[0], minProd = nums[0], answer = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) {
int tmp = maxProd; maxProd = minProd; minProd = tmp;
}
maxProd = Math.max(x, maxProd * x);
minProd = Math.min(x, minProd * x);
answer = Math.max(answer, maxProd);
}
return answer;
}
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int max_prod = nums[0], min_prod = nums[0], answer = nums[0];
for (int i = 1; i < nums.size(); i++) {
int x = nums[i];
if (x < 0) {
swap(max_prod, min_prod);
}
max_prod = max(x, max_prod * x);
min_prod = min(x, min_prod * x);
answer = max(answer, max_prod);
}
return answer;
}
};func maxProduct(nums []int) int {
maxProd, minProd, answer := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
x := nums[i]
if x < 0 {
maxProd, minProd = minProd, maxProd
}
maxProd = max(x, maxProd*x)
minProd = min(x, minProd*x)
answer = max(answer, maxProd)
}
return answer
}var maxProduct = function(nums) {
let maxProd = nums[0], minProd = nums[0], answer = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
if (x < 0) {
[maxProd, minProd] = [minProd, maxProd];
}
maxProd = Math.max(x, maxProd * x);
minProd = Math.min(x, minProd * x);
answer = Math.max(answer, maxProd);
}
return answer;
};function maxProduct(nums: number[]): number {
let maxProd = nums[0], minProd = nums[0], answer = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
if (x < 0) {
[maxProd, minProd] = [minProd, maxProd];
}
maxProd = Math.max(x, maxProd * x);
minProd = Math.min(x, minProd * x);
answer = Math.max(answer, maxProd);
}
return answer;
};其他解法
两种方法都是 O(n) 时间、O(1) 空间；动态规划靠状态转移处理负数，前缀积与后缀积靠两次扫描覆盖所有候选子数组。
解法 2：前缀积与后缀积 时间 O(n)，空间 O(1)
从左到右累乘得到前缀积，从右到左累乘得到后缀积，每一步都用当前积更新答案。累乘结果为 0 时，下一步从 1 重新开始。不含 0 的一段里，负数个数为偶数时整段最优；为奇数时，最优解一定是去掉最左或最右的那个负数之后的部分，正好被前缀积或后缀积覆盖。
不需要同时维护最大值和最小值，代码更短。正确性依赖对负数个数的分类讨论，不如动态规划容易推广到其他题。
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
answer = nums[0]
pre = suf = 0
for i in range(n):
pre = (pre or 1) * nums[i]
suf = (suf or 1) * nums[n - 1 - i]
answer = max(answer, pre, suf)
return answerclass Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
long answer = nums[0], pre = 0, suf = 0;
for (int i = 0; i < n; i++) {
pre = (pre == 0 ? 1 : pre) * nums[i];
suf = (suf == 0 ? 1 : suf) * nums[n - 1 - i];
answer = Math.max(answer, Math.max(pre, suf));
}
return (int) answer;
}
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
long long answer = nums[0], pre = 0, suf = 0;
for (int i = 0; i < n; i++) {
pre = (pre == 0 ? 1 : pre) * nums[i];
suf = (suf == 0 ? 1 : suf) * nums[n - 1 - i];
answer = max(answer, max(pre, suf));
}
return (int)answer;
}
};func maxProduct(nums []int) int {
n := len(nums)
answer, pre, suf := nums[0], 0, 0
for i := 0; i < n; i++ {
if pre == 0 {
pre = 1
}
if suf == 0 {
suf = 1
}
pre *= nums[i]
suf *= nums[n-1-i]
answer = max(answer, pre, suf)
}
return answer
}var maxProduct = function(nums) {
const n = nums.length;
let answer = nums[0], pre = 0, suf = 0;
for (let i = 0; i < n; i++) {
pre = (pre === 0 ? 1 : pre) * nums[i];
suf = (suf === 0 ? 1 : suf) * nums[n - 1 - i];
answer = Math.max(answer, pre, suf);
}
return answer;
};function maxProduct(nums: number[]): number {
const n = nums.length;
let answer = nums[0], pre = 0, suf = 0;
for (let i = 0; i < n; i++) {
pre = (pre === 0 ? 1 : pre) * nums[i];
suf = (suf === 0 ? 1 : suf) * nums[n - 1 - i];
answer = Math.max(answer, pre, suf);
}
return answer;
};