152. 乘积最大子数组

发表于 分类于 阅读次数： Waline： 本文字数： 613 阅读时长 ≈ 2 分钟

考点

  • 最大子数组和

思路

一、问题描述

给定一个整数数组 \[ \text{nums} = [a_0, a_1, \dots, a_{n-1}] \] 要求在所有连续子数组中，找出其元素乘积的最大值，并返回该最大乘积。

二、问题难点分析

与“最大子数组和”不同，本题的核心难点在于：

  • 负数的存在会改变乘积的符号
  • 一个当前看来很小的负数乘积，在遇到下一个负数后，可能变成极大的正数
  • 因此，仅维护“最大乘积”是不够的，还必须同时维护最小乘积

三、动态规划建模

1. 状态定义

在遍历数组时，对每个位置 \(i\) 定义两个状态：

  • \(\text{pre\_mx}\)：以位置 \(i-1\) 结尾的连续子数组的最大乘积
  • \(\text{pre\_mi}\)：以位置 \(i-1\) 结尾的连续子数组的最小乘积

在当前位置 \(i\)，需要基于这两个状态更新新的：

  • \(\text{cur\_mx}\)：以 \(i\) 结尾的最大乘积
  • \(\text{cur\_mi}\)：以 \(i\) 结尾的最小乘积

2. 初始条件（重点）

由于子数组必须是非空的连续区间，因此第一个元素必须作为起点： \[ \text{pre\_mx} = \text{pre\_mi} = \text{res} = a_0 \] 这是本题中最容易出错但至关重要的一步。

四、状态转移方程（重点）

设当前遍历到的元素为： \[ x = a_i \]

情况一：\(x \ge 0\)

正数不会改变符号： \[ \begin{aligned} \text{cur\_mx} &= \max(x,\; \text{pre\_mx} \times x) \\ \text{cur\_mi} &= \min(x,\; \text{pre\_mi} \times x) \end{aligned} \]

情况二：\(x < 0\)

负数会交换最大与最小的角色： \[ \begin{aligned} \text{cur\_mx} &= \max(x,\; \text{pre\_mi} \times x) \\ \text{cur\_mi} &= \min(x,\; \text{pre\_mx} \times x) \end{aligned} \]

状态更新

完成转移后，更新： \[ \text{pre\_mx} = \text{cur\_mx}, \quad \text{pre\_mi} = \text{cur\_mi} \]

五、答案维护（重点）

全局答案始终是所有位置“以当前位置结尾的最大乘积”中的最大值： \[ \text{res} = \max(\text{res},\; \text{cur\_mx}) \] 最终返回 res 即可。

六、算法复杂度

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)（仅使用常数额外变量）

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    static const int maxn = 2e4 + 5;
    int maxProduct(vector<int>& nums) {
        int pre_mi = nums[0], pre_mx = nums[0], res = nums[0];
        int cur_mx, cur_mi;
        for (int i = 1; i < nums.size(); ++i) {
            int x = nums[i];
            if (x >= 0)
                cur_mx = max(x, pre_mx * x), cur_mi = min(x, pre_mi * x);
            else
                cur_mx = max(x, pre_mi * x), cur_mi = min(x, pre_mx * x);
            res = max(res, cur_mx);
            pre_mi = cur_mi, pre_mx = cur_mx;
        }
        return res;
    }
};