LeetCode 152: Maximum Product Subarray (DP with Max/Min States)
LeetCode 152DPArrayToday we solve LeetCode 152 - Maximum Product Subarray.
Source: https://leetcode.com/problems/maximum-product-subarray/
English
Problem Summary
Given an integer array nums, find a contiguous non-empty subarray with the largest product and return that product.
Key Insight
Product behavior is different from sum: multiplying by a negative number can flip a very small (negative) product into a very large (positive) one. So at each index we must track both maxEndingHere and minEndingHere.
Brute Force and Limitations
Brute force checks all subarrays and multiplies elements, which is O(n^2) subarrays and can degrade further if multiplication is recomputed repeatedly. It is too slow for large inputs.
Optimal Algorithm Steps
1) Initialize maxEnd = minEnd = ans = nums[0].
2) For each next value x, if x < 0, swap maxEnd and minEnd (sign flip effect).
3) Update maxEnd = max(x, maxEnd * x) and minEnd = min(x, minEnd * x).
4) Update global answer: ans = max(ans, maxEnd).
Complexity Analysis
Time: O(n).
Space: O(1).
Common Pitfalls
- Tracking only maximum and ignoring minimum.
- Forgetting to swap max/min when current number is negative.
- Initializing with 0 instead of nums[0], which breaks all-negative cases.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxProduct(int[] nums) {
int maxEnd = nums[0];
int minEnd = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) {
int tmp = maxEnd;
maxEnd = minEnd;
minEnd = tmp;
}
maxEnd = Math.max(x, maxEnd * x);
minEnd = Math.min(x, minEnd * x);
ans = Math.max(ans, maxEnd);
}
return ans;
}
}func maxProduct(nums []int) int {
maxEnd, minEnd, ans := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
x := nums[i]
if x < 0 {
maxEnd, minEnd = minEnd, maxEnd
}
maxEnd = max(x, maxEnd*x)
minEnd = min(x, minEnd*x)
ans = max(ans, maxEnd)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxEnd = nums[0], minEnd = nums[0], ans = nums[0];
for (int i = 1; i < (int)nums.size(); ++i) {
int x = nums[i];
if (x < 0) swap(maxEnd, minEnd);
maxEnd = max(x, maxEnd * x);
minEnd = min(x, minEnd * x);
ans = max(ans, maxEnd);
}
return ans;
}
};class Solution:
def maxProduct(self, nums: list[int]) -> int:
max_end = min_end = ans = nums[0]
for x in nums[1:]:
if x < 0:
max_end, min_end = min_end, max_end
max_end = max(x, max_end * x)
min_end = min(x, min_end * x)
ans = max(ans, max_end)
return ansvar maxProduct = function(nums) {
let maxEnd = nums[0];
let minEnd = nums[0];
let ans = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
if (x < 0) {
[maxEnd, minEnd] = [minEnd, maxEnd];
}
maxEnd = Math.max(x, maxEnd * x);
minEnd = Math.min(x, minEnd * x);
ans = Math.max(ans, maxEnd);
}
return ans;
};中文
题目概述
给定整数数组 nums，请找出乘积最大的非空连续子数组，并返回该乘积。
核心思路
乘积题与和题最大区别在于“负数翻转”。一个很小的负积乘上负数后可能变成很大的正积。因此每一步都要同时维护：以当前位置结尾的最大乘积和最小乘积。
暴力解法与不足
暴力法枚举所有区间并计算乘积，至少 O(n^2)，输入稍大就会超时，且容易出现重复计算。
最优算法步骤
1）初始化 maxEnd = minEnd = ans = nums[0]。
2）遍历当前值 x，若 x < 0，先交换 maxEnd 与 minEnd。
3）更新 maxEnd = max(x, maxEnd * x)，minEnd = min(x, minEnd * x)。
4）用 ans = max(ans, maxEnd) 维护全局最优。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 只维护最大值，不维护最小值。
- 当前数为负时忘记交换 max/min。
- 初始化为 0，导致全负数组结果错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxProduct(int[] nums) {
int maxEnd = nums[0];
int minEnd = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) {
int tmp = maxEnd;
maxEnd = minEnd;
minEnd = tmp;
}
maxEnd = Math.max(x, maxEnd * x);
minEnd = Math.min(x, minEnd * x);
ans = Math.max(ans, maxEnd);
}
return ans;
}
}func maxProduct(nums []int) int {
maxEnd, minEnd, ans := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
x := nums[i]
if x < 0 {
maxEnd, minEnd = minEnd, maxEnd
}
maxEnd = max(x, maxEnd*x)
minEnd = min(x, minEnd*x)
ans = max(ans, maxEnd)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxEnd = nums[0], minEnd = nums[0], ans = nums[0];
for (int i = 1; i < (int)nums.size(); ++i) {
int x = nums[i];
if (x < 0) swap(maxEnd, minEnd);
maxEnd = max(x, maxEnd * x);
minEnd = min(x, minEnd * x);
ans = max(ans, maxEnd);
}
return ans;
}
};class Solution:
def maxProduct(self, nums: list[int]) -> int:
max_end = min_end = ans = nums[0]
for x in nums[1:]:
if x < 0:
max_end, min_end = min_end, max_end
max_end = max(x, max_end * x)
min_end = min(x, min_end * x)
ans = max(ans, max_end)
return ansvar maxProduct = function(nums) {
let maxEnd = nums[0];
let minEnd = nums[0];
let ans = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
if (x < 0) {
[maxEnd, minEnd] = [minEnd, maxEnd];
}
maxEnd = Math.max(x, maxEnd * x);
minEnd = Math.min(x, minEnd * x);
ans = Math.max(ans, maxEnd);
}
return ans;
};
Comments