动态规划题解——乘积最大子数组【LeetCode】

152. 乘积最大子数组

这道题的解法和思想和之前的一道题目非常相像，详情可见

数组题解——​最大子数组和​【LeetCode】（更新版）_leetcode 最大子数组-CSDN博客

一、算法逻辑（逐步思路）

❓ 题目描述：

给定一个整数数组 nums，找出一个连续子数组，使得乘积最大，返回这个最大乘积。

✅ 解题思路（动态规划）

1. 为什么需要同时维护最大值和最小值？

• 因为数组中可能有 负数，当两个负数相乘时会变成正数；
• 所以我们在每个位置都要维护两个状态：

• • f_max：以当前元素结尾的子数组的最大乘积；
  • f_min：以当前元素结尾的子数组的最小乘积。

2. 状态转移逻辑：

对当前元素 x，新的最大值和最小值可能由以下三者中的任一项决定：

• f_max * x（当前数乘上之前的最大乘积）；
• f_min * x（当前数乘上之前的最小乘积 → 负数翻转变大）；
• x 本身（新起一个子数组）；

所以转移写法为：

f_max, f_min = max(f_max * x, f_min * x, x), min(f_max * x, f_min * x, x)

3. 答案更新：

每次迭代后，用 ans = max(ans, f_max) 更新全局最大乘积。

4. 初始值设置：

• ans = -inf：防止全是负数或只有一个负数的情况；
• f_max = f_min = 1：初始乘积不影响第一位（或者你也可以初始化为 nums[0] 后从 nums[1:] 开始遍历）。

二、算法核心点

✅ 核心思想：乘积型动态规划 + 同时维护最大/最小子状态

• 因为负数存在“翻转符号”的作用，所以不能只维护最大乘积；
• 每一步都要考虑“以当前元素结尾”的最大/最小子数组；
• 类似于“滑动窗口动态规划”，但只保留一对值来优化空间。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -inf
        f_max = f_min = 1
        for x in nums:
            f_max, f_min = max(f_max*x, f_min*x, x), min(f_max*x, f_min*x, x)
            ans = max(ans, f_max)
        return ans

三、复杂度分析

• 时间复杂度：O(n)

• • 只遍历一遍数组，每次做常数次运算。

• 空间复杂度：O(1)

• • 只使用常数个变量（f_max、f_min、ans），无额外空间开销。

总结表：

✅ 举个例子帮助理解：

输入：nums = [2, 3, -2, 4]

最终结果是 6，即子数组 [2,3] 的乘积。