描述

输入一个长度为 $n$ 的整型数组 $nums$，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。

1.子数组是连续的，且最小长度为 $1$ ，最大长度为 $n$

2.长度为 $1$ 的子数组，乘积视为其本身，比如 $[4]$ 的乘积为 $4$

3.该题的数据保证最大的乘积不会超过 int 的范围，即不超过 $2^{32}-1$

数据范围:

$1<= n<=2×10^5$

$−100<= a[i]<=100$

输入描述：

第一行输入一个正整数 $n$ ，表示数组的长度

第二行输入 $n$ 个整数，表示数组中的值。

输出描述：

输出子数组的乘积的最大值

示例1

输入：

4
3 2 -2 4

输出：

6

说明：

子数组 $[3,2]$ 的乘积为 $6，[3,2,-1,4]$ 的乘积为 $-24，[4]$ 的乘积为 $4$，故返回 $6$

示例2

输入：

3
-3 0 -2

输出：

0

说明：

因为 $0$ 在中间，所有包含 $0$ 的子数组的乘积都为 $0$，另外的数都是负数，所以最大乘积的子数组为$[0]$，返回为$0$，因为子数组要求是连续的，所以 $[-3,-2]$ 不是 $[-3,0,-2]$ 的子数组，所以不能为 $6$，

示例3

输入：

3
-3 2 -2

输出：

12

题解

#include<iostream>
using namespace std;
const int N = 2e5+10;
int a[N];
int n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int mi = a[0], mx = a[0], res = a[0];
    for(int i = 1; i < n; i++) {
        int v1 = mi * a[i], v2 = mx * a[i];
        mx = max(a[i], max(v1, v2));
        mi = min(a[i], min(v1, v2));
        res = max(res, mx);
    }
    cout << res << endl;
    return 0;
}