题意概括

给定一个长度为 $n$ 的整数数组，要求找出这个数组中一个非空的连续子数组，使得这个子数组中所有元素的乘积最大。

数据范围:

• $1 \le n \le 10^5$
• $-100 \le \text{数组元素} \le 100$

基础知识

本题是动态规划 (Dynamic Programming) 的一个经典应用。

由于数组中存在负数，一个原本乘积最小的负数（绝对值很大），在乘以另一个负数后，可能就会变成乘积最大的正数。因此，在维护以当前位置 $i$ 结尾的“最大乘积”的同时，我们还需要维护以当前位置 $i$ 结尾的“最小乘积”。

我们定义 $mx_i$ 是以第 $i$ 个元素结尾的连续子数组的最大乘积， $mn_i$ 是以第 $i$ 个元素结尾的连续子数组的最小乘积。对于元素 $a_i$，状态转移方程如下：

$$mx_i = \max(a_i, a_i \times mx_{i-1}, a_i \times mn_{i-1}) $$$$mn_i = \min(a_i, a_i \times mx_{i-1}, a_i \times mn_{i-1}) $$

最终的答案是所有 $mx_i$ 中的最大值。注意到 $i$ 时刻的状态只与 $i-1$ 时刻有关，我们可以用两个变量进行滚动优化，将空间复杂度从 $O(n)$ 降为 $O(1)$。

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$（不计算存储输入数组的空间）。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 初始化结果以及dp变量
    ll ans = a[0];
    ll cmx = a[0];
    ll cmn = a[0];

    for (int i = 1; i < n; ++i) {
        ll x = a[i];
        
        // 如果当前数是负数, 最大和最小的角色会互换
        if (x < 0) {
           swap(cmx, cmn);
        }
        
        // 更新以 x 结尾的最大和最小子数组乘积
        cmx = max(x, cmx * x);
        cmn = min(x, cmn * x);
        
        // 更新全局最大乘积
        ans = max(ans, cmx);
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
4
2 3 -2 4
输出:
6

样例 2:
输入:
3
-2 3 -4
输出:
24
*/