乘积最大子数组

七崽爱吃小饼干2026/02/09阅读 0

乘积最大子数组

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

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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

codeType

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

示例 2:

codeType

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

提示:

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

解法

解法一：二维动态规划

这个解法会超内存

function maxProduct(nums: number[]): number {
    // 这题需要用二维动态规划
    // dp[i][j]表示i-j的子数组的乘积
    // dp[i][j]可以由dp[i][j-1] * nums[j]得到
    const n = nums.length
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
    let max = -Infinity
    for(let i = 0; i < n; i++){
        for(let j = i; j < n; j++){
            if(i === j){ // 长度为1时单独处理
                dp[i][j] = nums[i]
            }else{
                dp[i][j] = dp[i][j - 1] * nums[j]
            }
            max = Math.max(max, dp[i][j])
        }
    }
    return max
};

解法二

function maxProduct(nums: number[]): number {
    // F[i]如果表示以第i个元素为结尾的最大连续子数组的乘积
    // 一般可以有F[i] = F[i - 1] * nums[i]
    // 但是这题中有负数，所以需要维护两个数组
    // Fmax同F[i]
    // Fmin表示以第i个元素为结尾的 最小 连续子数组的乘机
    // Fmax[i]和Fmin[i]可以由Fmax[i-1]以及Fmin[i-1]得到
    // Fmax[i] = max(Fmax[i - 1] * nums[i], Fmin[i - 1] * nums[i], nums[i])
    // Fmin[i] = min(Fmax[i - 1] * nums[i], Fmin[i - 1] * nums[i], nums[i])
    const n = nums.length
    const Fmax = new Array(n).fill(0)
    const Fmin = new Array(n).fill(0)
    Fmax[0] = nums[0]
    Fmin[0] = nums[0]
    let max = nums[0]
    for(let i = 1; i < n; i++){
        Fmax[i] = Math.max(Fmax[i - 1] * nums[i], Fmin[i - 1] * nums[i], nums[i])
        Fmin[i] = Math.min(Fmax[i - 1] * nums[i], Fmin[i - 1] * nums[i], nums[i])
        max = Math.max(Fmax[i], max)
    }
    return max
};