好的，我为你介绍一个线性动态规划领域里非常经典且实用的题目。根据你的要求，它不在你给出的已讲题目列表中。
题目：线性动态规划：乘积最大子数组
题目描述
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组至少包含一个数字），并返回该子数组所对应的乘积。
示例 1：
输入: nums = [2, 3, -2, 4]
输出: 6
解释: 子数组 [2, 3] 有最大乘积 6。
示例 2：
输入: nums = [-2, 0, -1]
输出: 0
解释: 结果不能为 2，因为 [-2, -1] 不是连续子数组。乘积最大子数组是 [0]，乘积为 0。
注意： 测试用例的答案是一个 32位 整数。数组中的元素可以是负数、零和正数。乘积可能会非常大（包括负数），所以简单的最大值递推会失效，因为我们不仅要记录最大乘积，还需要记录可能因后续遇到负数而“翻身”的最小乘积（负得最多的那个数）。
解题过程循序渐进讲解
第一步：理解问题的核心矛盾与关键观察
这个问题的核心在于负数的存在以及连续性。
- 连续性：我们要求的是连续子数组，而不是可以跳跃选取的子序列。
- 负数的影响：
- 正数乘以正数，结果变大。
- 负数乘以负数，结果会“负负得正”，变得更大。
- 零会“重置”所有累积的乘积。
这个特性意味着，对于以当前元素 nums[i] 结尾的子数组，其最大乘积不仅取决于上一个状态的最大乘积 maxProd[i-1]，还取决于上一个状态的最小乘积 minProd[i-1]（因为当前元素可能是负数）。
关键观察：对于以位置 i 结尾的子数组，其最大乘积可能来自以下三种情况之一：
nums[i]自己（例如，前面是0，或者当前数非常大）。nums[i] * maxProd[i-1]（例如，nums[i]是正数，乘上之前的最大正数积）。nums[i] * minProd[i-1]（例如，nums[i]是负数，乘上之前“负得最多”的积，反而能得到一个大的正数）。
同样，以位置 i 结尾的子数组，其最小乘积也可能来自：
nums[i]自己。nums[i] * maxProd[i-1]（例如，nums[i]是负数，乘上一个大正数，会变成一个大负数）。nums[i] * minProd[i-1]（例如，nums[i]是正数，乘上一个很小的负数，还是一个很小的负数）。
第二步：定义动态规划状态
基于以上分析，我们需要两个动态规划数组（或变量）来同时追踪状态：
maxDP[i]：表示以第i个元素结尾的连续子数组的最大乘积。minDP[i]：表示以第i个元素结尾的连续子数组的最小乘积（通常是负数，但也是乘积最大的负数）。
我们的最终答案是所有 maxDP[i] 中的最大值。
第三步：推导状态转移方程
对于每个位置 i（i >= 1），我们需要用 maxDP[i-1]、minDP[i-1] 和 nums[i] 来更新 maxDP[i] 和 minDP[i]。
状态转移方程如下：
-
更新
maxDP[i]：它应该是下面三个值的最大值。nums[i]： 子数组只包含它自己。nums[i] * maxDP[i-1]： 当前数乘以前面的最大乘积。nums[i] * minDP[i-1]： 当前数乘以前面的最小乘积（负负得正）。
所以：
maxDP[i] = max(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1]) -
更新
minDP[i]：它应该是下面三个值的最小值（用于未来可能遇到负数时“翻身”）。nums[i]nums[i] * maxDP[i-1]（正数乘大负数，或负数乘大正数，都可能导致很小的负数）nums[i] * minDP[i-1]
所以：
minDP[i] = min(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1])
初始化：
- 当
i = 0时，以第一个元素结尾的子数组只有它自己。所以：maxDP[0] = nums[0]minDP[0] = nums[0]- 全局答案
ans初始化为nums[0]
第四步：逐步演算示例
让我们用示例 nums = [2, 3, -2, 4] 来走一遍流程。
下标 i |
nums[i] |
计算过程 | maxDP[i] |
minDP[i] |
更新全局答案 ans |
|---|---|---|---|---|---|
| 0 | 2 | 初始化 | 2 | 2 | 2 |
| 1 | 3 | max(3, 3*2, 3*2) = max(3, 6, 6) = 6 min(3, 3*2, 3*2) = min(3, 6, 6) = 3 |
6 | 3 | max(2, 6) = 6 |
| 2 | -2 | max(-2, -2*6, -2*3) = max(-2, -12, -6) = -2 min(-2, -2*6, -2*3) = min(-2, -12, -6) = -12 |
-2 | -12 | max(6, -2) = 6 |
| 3 | 4 | max(4, 4*(-2), 4*(-12)) = max(4, -8, -48) = 4 min(4, 4*(-2), 4*(-12)) = min(4, -8, -48) = -48 |
4 | -48 | max(6, 4) = 6 |
最终结果：全局答案 ans = 6，对应子数组 [2, 3]。
第五步：空间优化（可选但推荐）
观察状态转移方程，maxDP[i] 和 minDP[i] 只依赖于前一个状态 maxDP[i-1] 和 minDP[i-1]。因此，我们不需要维护整个数组，只需要两个变量来滚动记录前一个状态即可。
优化后的步骤：
- 初始化：
curMax = nums[0]curMin = nums[0]ans = nums[0]
- 从
i = 1开始遍历数组：- 由于计算
curMax和curMin需要用到旧的curMax和curMin，我们必须先把它们暂存起来，否则更新curMax后，计算curMin用的就是新的错误值。 - 令
tempMax = curMax,tempMin = curMin。 - 更新：
curMax = max(nums[i], nums[i] * tempMax, nums[i] * tempMin)curMin = min(nums[i], nums[i] * tempMax, nums[i] * tempMin)
- 更新全局答案：
ans = max(ans, curMax)
- 由于计算
第六步：代码实现（Python示例）
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
# 初始化
cur_max = cur_min = ans = nums[0]
# 从第二个元素开始遍历
for i in range(1, len(nums)):
num = nums[i]
# 暂存旧值
temp_max, temp_min = cur_max, cur_min
# 更新当前最大值和最小值
cur_max = max(num, num * temp_max, num * temp_min)
cur_min = min(num, num * temp_max, num * temp_min)
# 更新全局最大乘积
ans = max(ans, cur_max)
return ans
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
总结
这道题通过引入两个互补的状态（maxDP 和 minDP），巧妙地解决了负数对连续子数组乘积的影响问题。其核心思想是：当前位置的最优解可能由历史最优解、历史最差解和当前值共同决定。这是动态规划中一种非常典型的状态设计思路，尤其在处理具有“符号翻转”特性的最优化问题时非常有效。