题解 | #连续子数组的最大乘积#

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

int arr[200005];

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {

        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);

        }
        if (n == 1) {
            printf("%d\n", arr[0]);
            continue;
        }

        int maxnum = arr[0], minnum = arr[0];
        int res = arr[0];
        for (int i = 1; i < n; i++) {
            int mx = maxnum, mn = minnum;
            //为什么要保存下Maxnum和minnum的值呢？
            //如果不保存这两个值，第一条语句maxnum没问题，但在第二条语句的时候用到的maxnum要求是之前的，
            //而如今maxnum已经更新，所以要想找到之前的maxnum，必须要保存起来
            maxnum = max(mx * arr[i], max(arr[i], mn * arr[i]));
            minnum = min(mn * arr[i], min(arr[i], mx * arr[i]));
            res = max(res, maxnum);
        }
        /*  错误的写法
            for (int i = 1; i < n; i++) {
                maxnum = max(maxnum * arr[i], max(arr[i], minnum * arr[i]));
                minnum = min(minnum * arr[i], min(arr[i], maxnum * arr[i]));
                printf("maxnum=%d minnum=%d\n", maxnum, minnum);
                res = max(res, maxnum);
            }
        */
        printf("%d\n", res);

    }
}

要动态维护两个值maxnum和minnum,代表的值在第i - 1的位置，最小的乘积和最大的乘积分别是多少，如果当前i位置是一个正数，那么就会希望maxnum尽可能的大，如果i位置是一个负数，就会希望minnum尽可能的小。

以此遍历来找到最大值