LeetCode152.乘积最大子数组

更新: 4/20/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode152.乘积最大子数组

题目意思很简单，就是要找到一个连续的子数组，使得子数组的乘积最大，要求你返回这个最大值，其中，数组中的元素是可能存在负数的。

因为数据范围：$1<=nums.length<=2\ast {10}^4$，所以这里$O(n^2)$的时间复杂度是会超时的，所以我们得优化时间复杂度，这里考虑下动态规划。

我们设$f[i]$为以第$i$个数字结尾的子数组所能得到的最大乘积，那么我们很容易想到状态转移方程：

$f[i]=max(f[i-1]\ast nums[i],f[i])$

要么就是把前一个最大的连续子数组加上当前这个，要么就不加，取最大值即可，然后我们可以得出如下代码：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int f[20005];
        int n = nums.size();
        for(int i = 0;i < n;i++)f[i] = nums[i];
        for(int i = 1;i < n;i++) {
            f[i] = max(f[i - 1] * nums[i], f[i]);
        }
        int ans = INT_MIN;
        for(int i = 0;i < n;i++)ans = max(ans, f[i]);
        return ans;
    }
};

但这样过不了全部样例，会被这么一组数据卡掉：

nums =
[-2,3,-4]

输出:3
预期结果:4

我们发现，按照我们上面的思路,$f[1]$得出来是3，$f[2]$得出来是-4（-12<-4），但我们可以发现乘起来是24，说明我们上面的思路有问题。

我们可以发现，如果当前数是负数，那么此时应该取上一个的负数值来乘（比如-4×-2比-4×-1要打），所以我们对于每一个数应该根据正负号进行分别判断，由上面分析可知我们还需要维护一个最小值，那么最终代码就出来了。

$Solution$:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int f[20005], f_min[20005];
        int n = nums.size();
        for(int i = 0;i < n;i++)f[i] = nums[i], f_min[i] = nums[i];
        for(int i = 1;i < n;i++) {
            if(nums[i] < 0) {
                f[i] = max(f[i], f_min[i - 1] * nums[i]);
                f_min[i] = min(f_min[i], f[i - 1] * nums[i]);
            } else {
                f[i] = max(f[i], f[i - 1] * nums[i]);
                f_min[i] = min(f_min[i], f_min[i - 1] * nums[i]);
            }
        }
        int ans = INT_MIN;
        for(int i = 0;i < n;i++)ans = max(ans, f[i]);
        return ans;
    }
};