当前位置：首页 > backend >正文

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

backend 2025/7/15 15:49:40

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 = -inff_max = f_min = 1for 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），无额外空间开销。

总结表：

维度	内容
✅ 思路逻辑	遍历数组时维护以当前位置结尾的最大/最小乘积，更新全局最大值
✅ 核心技巧	负数会导致最大最小翻转，必须同时维护最大值和最小值
✅ 时间复杂度	O(n) 一次遍历
✅ 空间复杂度	O(1) 使用常数变量优化