LeetCode 152 乘积最大子数组：动态规划同时维护最大最小值

题目描述

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

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

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

提示

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都保证是一个 32-位 整数

解题思路

方法：动态规划

由于负数的存在，我们需要同时记录最大值和最小值。关键点：

使用两个变量记录当前最大值和最小值
对于每个数字，考虑与当前最大值和最小值相乘的情况
更新最大值和最小值
更新全局最大值

时间复杂度：O(n)，其中n是数组长度。空间复杂度：O(1)，只需要常数级别的额外空间。

代码实现

C# 实现

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxProduct = nums[0];
        int currentMax = nums[0];
        int currentMin = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            int temp = currentMax;
            currentMax = Math.Max(Math.Max(nums[i], currentMax * nums[i]), currentMin * nums[i]);
            currentMin = Math.Min(Math.Min(nums[i], temp * nums[i]), currentMin * nums[i]);
            maxProduct = Math.Max(maxProduct, currentMax);
        }
        
        return maxProduct;
    }
}

Python 实现

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_product = nums[0]
        current_max = nums[0]
        current_min = nums[0]
        
        for num in nums[1:]:
            temp = current_max
            current_max = max(num, current_max * num, current_min * num)
            current_min = min(num, temp * num, current_min * num)
            max_product = max(max_product, current_max)
            
        return max_product

C++ 实现

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxProduct = nums[0];
        int currentMax = nums[0];
        int currentMin = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            int temp = currentMax;
            currentMax = max({nums[i], currentMax * nums[i], currentMin * nums[i]});
            currentMin = min({nums[i], temp * nums[i], currentMin * nums[i]});
            maxProduct = max(maxProduct, currentMax);
        }
        
        return maxProduct;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	实现简洁，性能适中
Python	156 ms	16.8 MB	代码最简洁
C++	24 ms	9.6 MB	性能最优

补充说明

代码亮点

使用动态规划思想，同时维护最大值和最小值
处理了负数的情况
空间复杂度为O(1)

常见错误

没有考虑负数的情况
没有处理数组长度为1的情况
没有考虑整数溢出的情况

讨论

有几个问题可以思考一下：

为什么要同时维护最大值和最小值？只维护最大值不行吗？
负数乘以负数会变成正数，这个特性在这道题中怎么利用的？
这道题和第53题（最大子数组和）有什么异同？

欢迎在评论区讨论。

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。