152. 乘积最大子数组

难度：🟡 Medium | 标签：动归 | 状态：⬜ LeetCode 链接

思路

负数会翻转最大最小，所以同时维护「以 i 结尾」的最大乘积 mx 和最小乘积 mn。 新元素加入时：候选三个 x, mx*x, mn*x，取 max / min。

代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int mx = nums[0], mn = nums[0], best = nums[0];
        for (int i = 1; i < (int)nums.size(); ++i) {
            int x = nums[i];
            int a = mx * x, b = mn * x;
            mx = max({x, a, b});
            mn = min({x, a, b});
            best = max(best, mx);
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 必须同时维护 max 和 min，不能只算 max
• max({x, a, b}) 用 initializer_list 形式
• 不要写 mx = max(mx * x, ...)——这是上一轮的 mx 已被覆盖