152. 乘积最大子数组

[S-T-D]

• 原题地址
• 题目描述
• 题解 —— 暴力
  • 思路
  • 代码
  • 复杂度
• 题解 —— 动态规划
  • 思路
  • 代码
  • 复杂度
     

原题地址

152. 乘积最大子数组

 

题目描述

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

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

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

 

题解 —— 暴力

思路

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    const len = nums.length;
    if (len === 0) return 0;
    if (len === 1) return nums[0];

    let single, cur, prev;
    let res = -Infinity;
    for (let i = 0; i < len; i++) {
        single = nums[i];
        prev = single;
        res = Math.max(res, single);
        for (let j = i + 1; j < len; j++) {
            cur = prev * nums[j];
            prev = cur;
            res = Math.max(res, cur);
        }
    }

    return res;
};

复杂度

• 时间：O(n^2)
• 空间：O(1)

 

题解 —— 动态规划

思路

参考官方题解。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let res = nums[0];
    let maxp = nums[0];
    let minp = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const cur = nums[i];
        const tmax = maxp;
        const tmin = minp;
        maxp = Math.max(cur, tmax * cur, tmin * cur);
        minp = Math.min(cur, tmax * cur, tmin * cur);
        res = Math.max(res, maxp);
    }
    return res;
};

复杂度

• 时间：O(n)
• 空间：O(1)