题目描述

给你一个整数数组，请找出连续的一段，使得这段数组中所有数的乘积最大。

样例1

输入：[2,3,-2,4]
输出：6
解释：[2,3] 的乘积最大，是6.

样例2

输入：[-2,0,-1]
输出：0
解释：结果不能是2, 因为 [-2,-1] 不是连续的一段.

算法

(贪心) $O(n)$

首先考虑暴力做怎么做：可以枚举连续子段的终点，然后顺次往前枚举连续子段的起点，直到遇到0，或者遍历到数组第一个元素为止。

分析整个过程我们会发现：对于每个终点 $i$，我们枚举 $j = i-1,i-2,…$时，$nums[j] \times nums[j+1] \times … \times nums[i]$的绝对值是单调递增的，因此满足 $nums[j] \times nums[j+1] \times … \times nums[i] \gt 0$的最小的 $j$，就是我们要求的起点！

所以我们可以在扫描数组时维护两个值：与当前元素相邻的绝对值最大的正数乘积 $pos$ 和负数乘积 $neg$。当我们枚举到 $i$ 时：

• 如果 $nums[i] \gt 0$，则 $nums[i] \times pos$ 就是以 $i$ 为终点的最大乘积；
• 如果 $nums[i] \lt 0$，则 $nums[i] \times neg$ 就是以 $i$ 为终点的最大乘积；

然后用 $nums[i] * pos$ 和 $nums[i] * neg$ 更新 $pos$ 和 $neg$ 的值。

时间复杂度分析：整个数组仅被遍历一次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int pos = 0, neg = 0;
        int res = INT_MIN;
        for (auto x : nums)
        {
            if (x > 0)
            {
                if (pos > 0) pos *= x;
                else pos = x;
                neg *= x;
            }
            else if (x < 0)
            {
                int np = pos, ng = neg;
                np = neg * x;
                if (pos > 0) ng = pos * x;
                else ng = x;
                pos = np, neg = ng;
            }
            else
            {
                pos = neg = 0;
            }
            res = max(res, x);
            if (pos != 0) res = max(res, pos);
        }
        return res;
    }
};