LeetCode 152. 乘积最大子数组

◎

本节目标

同时维护以当前位置结尾的最大和最小乘积，处理负数翻转。

这是动态规划基础与线性状态中多状态滚动的母题。

题意与约束

求非空连续子数组的最大乘积；负数会把较小的负乘积翻转成最大候选。

第一反应与重复子问题

只保存当前最大乘积不够：下一个负数会需要此前最小乘积，因此两个“以当前位置结尾”的状态都要保留。

状态定义与转移推导

令 largest、smallest 为当前位置结尾的最大和最小乘积。遇负数先交换二者，再分别与当前元素比较更新。

正确性依据

以当前位置结尾的连续段只能从当前元素重开，或把上一段乘上当前元素。正数保持大小关系，负数交换大小关系，两个极值已覆盖所有最优候选。

样例执行过程

[-2,3,-4] 中，末尾 -4 令此前最小乘积 -6 翻转为 24。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int largest = nums[0], smallest = nums[0], answer = nums[0];
        for (int index = 1; index < static_cast<int>(nums.size()); index++) {
            int value = nums[index];
            if (value < 0) {
                swap(largest, smallest);
            }
            largest = max(value, largest * value);
            smallest = min(value, smallest * value);
            answer = max(answer, largest);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        largest = smallest = answer = nums[0]
        for value in nums[1:]:
            if value < 0:
                largest, smallest = smallest, largest
            largest = max(value, largest * value)
            smallest = min(value, smallest * value)
            answer = max(answer, largest)
        return answer

复杂度分析

时间 O(n)，状态数固定，空间 O(1)。

边界与易错点

• 零会使连续乘积重新开始。
• 处理负数必须在计算新状态前交换旧极值。

模式迁移

凡是转移会改变状态排序的题，都要记录足够的极值或符号状态，而不能只保留一个最优值。