题目

思路

一句话：对于“以当前位置结尾的子数组”，同时记录它能得到的最大乘积和最小乘积，负数一来就“正负互换”。

先想最直白的：枚举所有起点 i、终点 j，再把这一段乘起来。最差要 O(n³)；即使用“边扫边乘”优化成 O(n²)，n 最大 2 × 10⁴，也跑不动。

关键观察：乘积不是求和，乘一个负数会把符号翻过来。比如到 i 结尾，最大的乘积不一定来自“之前的最大”，还可能来自“之前的最小”——一个很负的数乘负数反而变大。所以只看一个最大值会丢信息。

因此每个位置维护两个状态：curMax = 以当前元素结尾的子数组的最大乘积，curMin = 最小乘积。下一步在「接上 curMax、接上 curMin、直接从当前元素另起炉灶」三者里取最大 / 最小。这样一次遍历就能搞定。

解法

状态：curMax[i] / curMin[i] 分别表示必须以 nums[i] 结尾的子数组的最大 / 最小乘积。

转移（对当前数 n）：

• fromMax = curMax × n（接上最大）
• fromMin = curMin × n（接上最小）
• curMax = max(n, fromMax, fromMin) —— 其中 n 表示从当前位置新开子数组
• curMin = min(n, fromMax, fromMin)
• 用 curMax 更新答案。

因为当前状态只依赖上一步，两个变量滚动即可。

看第 4 行：接最大得到 -12，但“接最小”反而得到 24，这就是必须保留最小值的理由。

下图把上面 5 个步骤串成流程，并逐步演示：

C++

#include <algorithm>
#include <vector>
using namespace std;  class Solution {
public:
 int maxP
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。