vvrf / DSA.log

问题拆解

在数组里找一个连续子数组，让它的乘积最大。看起来和“最大子数组和”是一道题换了个运算符，照搬那套做法——维护“以 i 结尾的最大和”——却会在负数上翻车：一个很小的负积，乘上一个负数，可能一跃成为最大积。

比如 [-2, 3, -4]。走到 -4 时，以它结尾的最大积是 (-2) * 3 * (-4) = 24，它的来源恰恰是前一步的最小积 -6。也就是说，只记最大值会把未来的答案丢掉。

关键观察：以 i 结尾的最大积，只可能来自三个候选——nums[i] 自己、前一步最大积乘 nums[i]、前一步最小积乘 nums[i]。最小积同理。所以把两条状态一起往前滚就够了。

乘法没有单调性：正数保序，负数反序。凡是运算会“翻转大小关系”的 DP，就要把最大和最小两个极端一起带着走。

同时滚动最大积与最小积

一个小技巧：当 nums[i] 是负数时，先把最大积和最小积互换，之后的转移就和正数完全一样，不用写三元比较。

public int maxProduct(int[] nums) {
    int ans = nums[0], maxProd = nums[0], minProd = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        if (x < 0) { // 负数把最大最小对调
            int t = maxProd;
            maxProd = minProd;
            minProd = t;
        }
        maxProd = Math.max(x, maxProd * x); // 要么接上前缀，要么另起炉灶
        minProd = Math.min(x, minProd * x);
        ans = Math.max(ans, maxProd);
    }
    return ans;
}

def maxProduct(nums: List[int]) -> int:
    ans = max_prod = min_prod = nums[0]
    for x in nums[1:]:
        if x < 0:  # 负数把最大最小对调
            max_prod, min_prod = min_prod, max_prod
        max_prod = max(x, max_prod * x)  # 要么接上前缀，要么另起炉灶
        min_prod = min(x, min_prod * x)
        ans = max(ans, max_prod)
    return ans

func maxProduct(nums []int) int {
    ans, maxProd, minProd := nums[0], nums[0], nums[0]
    for _, x := range nums[1:] {
        if x < 0 { // 负数把最大最小对调
            maxProd, minProd = minProd, maxProd
        }
        maxProd = max(x, maxProd*x) // 要么接上前缀，要么另起炉灶
        minProd = min(x, minProd*x)
        ans = max(ans, maxProd)
    }
    return ans
}

pub fn max_product(nums: Vec<i32>) -> i32 {
    let mut ans = nums[0];
    let (mut max_prod, mut min_prod) = (nums[0], nums[0]);
    for &x in &nums[1..] {
        if x < 0 {
            // 负数把最大最小对调
            std::mem::swap(&mut max_prod, &mut min_prod);
        }
        max_prod = x.max(max_prod * x); // 要么接上前缀，要么另起炉灶
        min_prod = x.min(min_prod * x);
        ans = ans.max(max_prod);
    }
    ans
}

每一步转移里的 max(x, ...) 不能省：它对应“不要前面的乘积，从自己重新开始”，专门处理前缀里出现 0（乘积被清零，接着乘只会是 0）的情况。另一个易错点是答案要在循环里逐步取最大——最大积以哪个下标结尾是不知道的，不能只看最后一个状态。

复杂度

指标	复杂度	原因
时间	`O(n)`	一次遍历，每个元素常数次乘法比较
空间	`O(1)`	只滚动最大积、最小积、答案三个变量

可以迁移的模式

转移运算会翻转大小关系时（乘负数、取相反数），最优解可能藏在“最劣状态”里，两个极端要一起维护；
“以 i 结尾”的状态定义配上“要么延续、要么重开”的转移，是子数组类 DP 的标准骨架；
答案沿途收集，而不是只看最后一个状态。

把“最大子数组和”里的一条状态拆成两条，这道题就解完了——差别全在负数身上。