乘积最大子数组 图解题解

乘积最大子数组难在哪

在数组 nums 里找一段连续子数组，使所有元素的乘积最大，返回这个乘积。数组里混着正数和负数（还可能有 0），这正是难点：加法世界里「越加越大」的直觉，在乘法世界被负号打碎——一个负数把大变小、把小变大，两个负数相乘又翻回正。比如 nums = [2,3,-2,4,-1,2,1,-5,4,3] 的答案是 480，靠的恰恰是负数之间的配合。

为什么照搬最大子数组和的套路会漏解

这题长得很像 LeetCode 53 最大子数组和，那题只维护一个状态：以当前元素结尾的最大和。照搬到乘法上——只维护「以当前元素结尾的最大乘积」——会立刻漏解：一段乘积是 -48 的前缀在「最大」的眼里一文不值，早被丢弃；可它后面若跟着一个 -1，乘起来就是 48，反而是全场希望最大的种子。

关键观察由此而来：乘法里「当前最小」和「当前最大」同样有前途，一个负数就能让两者互换身份。所以状态必须成对维护——最大乘积 imax 和最小乘积 imin 缺一不可，让最负的那条线也活着，等负数来接它翻身。

imax 和 imin 两个状态怎么定义

定义 imax 为「以当前元素结尾的连续子数组的最大乘积」，imin 为同一口径下的最小乘积，二者都强制「以当前元素结尾」——这保证子数组连续，也让下一个元素能直接接在后面。全局答案 ans 则是历史上所有 imax 中的最大者，因为最优子数组总得以某个位置收尾，逐位收集就不会错过。三个变量都用 nums[0] 初始化，从第二个元素起逐个转移。

遇到负数为什么要先交换再转移

对每个新元素 x，以 x 结尾的子数组只有两种形态：x 自己另起一段，或接在前一段后面。所以 imax = max(x, imax * x)、imin = min(x, imin * x)。但若 x 是负数，乘法会把大小关系整体翻转——原来最大的乘完变最小，原来最小的乘完变最大。先把 imax 与 imin 交换再套同一组转移式，等价于让 x 去乘「乘完它之后会变大的那一条」，两条候选线都不丢。交换必须发生在转移之前，写反了两个状态全错。

「和 x 本身比」这一半也不可省：遇到 0 或前段乘积方向不利时，max(x, imax * x) 允许从 x 重新起段，把拖后腿的前缀干净地甩掉，0 自然成为分段点。

复杂度多少，最容易错在哪

每个元素只做常数次比较和乘法，一遍扫描，时间 O(n)；全程只有 imax、imin、ans 三个变量，空间 O(1)。

三个高频翻车点复盘：只维护 imax 不维护 imin，负负得正的翻身仗直接打不了；转移时忘了和 x 本身比，被 0 或反号的前缀拖死；交换写在转移之后，负数一来两个状态同时污染。记住一句话就够了——加法只用记最大，乘法要最大最小成对记，遇负先换位。

Python

def maxProduct(nums):
    imax = imin = ans = nums[0]
    for x in nums[1:]:
        if x < 0: imax, imin = imin, imax
        imax = max(x, imax * x)
        imin = min(x, imin * x)
        ans = max(ans, imax)
    return ans

C++

int maxProduct(vector<int>& nums){
    int imax = nums[0], imin = nums[0], ans = nums[0];
    for(int i = 1; i < nums.size(); i++){
        int x = nums[i];
        if(x < 0) swap(imax, imin);
        imax = max(x, imax * x);
        imin = min(x, imin * x);
        ans = max(ans, imax);
    }
    return ans;
}

Java

int maxProduct(int[] nums){
    int imax = nums[0], imin = nums[0], ans = nums[0];
    for(int i = 1; i < nums.length; i++){
        int x = nums[i];
        if(x < 0){ int t = imax; imax = imin; imin = t; }
        imax = Math.max(x, imax * x);
        imin = Math.min(x, imin * x);
        ans = Math.max(ans, imax);
    }
    return ans;
}