Medium

题目描述

给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32位 整数

解题思路

这道题是经典的动态规划问题，但与最大子数组和不同的是，乘积运算有其特殊性：

核心思路分析：

  1. 负数的特殊性：两个负数相乘得正数，所以我们需要同时维护最大值和最小值
  2. 零的影响：遇到0时乘积重置为0，需要重新开始计算

动态规划状态设计：

  • maxDP[i]：以 nums[i] 结尾的子数组的最大乘积
  • minDP[i]：以 nums[i] 结尾的子数组的最小乘积

状态转移方程：

maxDP[i] = max(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])
minDP[i] = min(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])

优化思路： 由于每个状态只依赖前一个状态，可以用两个变量代替数组，将空间复杂度优化到O(1)。

算法步骤：

  1. 初始化最大值、最小值和结果
  2. 遍历数组，动态更新当前最大值和最小值
  3. 每次更新结果为历史最大值

这种方法能够正确处理负数、零和正数的所有组合情况。

代码实现

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxVal = nums[0];
        int minVal = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < 0) {
                swap(maxVal, minVal);
            }
            
            maxVal = max(nums[i], maxVal * nums[i]);
            minVal = min(nums[i], minVal * nums[i]);
            
            result = max(result, maxVal);
        }
        
        return result;
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_val = nums[0]
        min_val = nums[0]
        result = nums[0]
        
        for i in range(1, len(nums)):
            if nums[i] < 0:
                max_val, min_val = min_val, max_val
            
            max_val = max(nums[i], max_val * nums[i])
            min_val = min(nums[i], min_val * nums[i])
            
            result = max(result, max_val)
        
        return result

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxVal = nums[0];
        int minVal = nums[0];
        int result = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < 0) {
                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
            }
            
            maxVal = Math.Max(nums[i], maxVal * nums[i]);
            minVal = Math.Min(nums[i], minVal * nums[i]);
            
            result = Math.Max(result, maxVal);
        }
        
        return result;
    }
}

var maxProduct = function(nums) {
    let maxVal = nums[0];
    let minVal = nums[0];
    let result = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            [maxVal, minVal] = [minVal, maxVal];
        }
        
        maxVal = Math.max(nums[i], maxVal * nums[i]);
        minVal = Math.min(nums[i], minVal * nums[i]);
        
        result = Math.max(result, maxVal);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，其中 n 为数组长度
空间复杂度O(1)只使用常数个额外变量存储状态

相关题目