Question

152. 乘积最大子数组

English Version

题目描述

给你一个整数数组 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 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

解法

方法一：动态规划

我们定义两个变量 $f$ 和 $g$，其中 $f$ 表示以 $nums[i]$ 结尾的乘积最大子数组的乘积，而 $g$ 表示以 $nums[i]$ 结尾的乘积最小子数组的乘积。初始时 $f$ 和 $g$ 都等于 $nums[0]$。答案为所有 $f$ 中的最大值。

从 $i=1$ 开始，我们可以考虑将第 $i$ 个数 $nums[i]$ 添加到前面的乘积最大或者乘积最小的子数组乘积的后面，或者单独作为一个子数组乘积（即此时子数组长度只有 $1$）。我们将此前的乘积最大值记为 $ff$，乘积最小值记为 $gg$，那么 $f = \max(f, ff \times nums[i], gg \times nums[i])$，而 $g = \min(g, ff \times nums[i], gg \times nums[i])$。接下来，我们更新答案 $ans = \max(ans, f)$，然后继续计算下一个位置。

最后的答案即为 $ans$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。我们只需要遍历数组一次即可求得答案。空间复杂度 $O(1)$。

class Solution:
  def maxProduct(self, nums: List[int]) -> int:
    ans = f = g = nums[0]
    for x in nums[1:]:
      ff, gg = f, g
      f = max(x, ff * x, gg * x)
      g = min(x, ff * x, gg * x)
      ans = max(ans, f)
    return ans

class Solution {
  public int maxProduct(int[] nums) {
    int f = nums[0], g = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; ++i) {
      int ff = f, gg = g;
      f = Math.max(nums[i], Math.max(ff * nums[i], gg * nums[i]));
      g = Math.min(nums[i], Math.min(ff * nums[i], gg * nums[i]));
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

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

func maxProduct(nums []int) int {
  f, g, ans := nums[0], nums[0], nums[0]
  for _, x := range nums[1:] {
    ff, gg := f, g
    f = max(x, max(ff*x, gg*x))
    g = min(x, min(ff*x, gg*x))
    ans = max(ans, f)
  }
  return ans
}

function maxProduct(nums: number[]): number {
  let [f, g, ans] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    const [ff, gg] = [f, g];
    f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
    g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
    ans = Math.max(ans, f);
  }
  return ans;
}

impl Solution {
  pub fn max_product(nums: Vec<i32>) -> i32 {
    let mut f = nums[0];
    let mut g = nums[0];
    let mut ans = nums[0];
    for &x in nums.iter().skip(1) {
      let (ff, gg) = (f, g);
      f = x.max(x * ff).max(x * gg);
      g = x.min(x * ff).min(x * gg);
      ans = ans.max(f);
    }
    ans
  }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let [f, g, ans] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; ++i) {
    const [ff, gg] = [f, g];
    f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
    g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
    ans = Math.max(ans, f);
  }
  return ans;
};

public class Solution {
  public int MaxProduct(int[] nums) {
    int f = nums[0], g = nums[0], ans = nums[0];
    for (int i = 1; i < nums.Length; ++i) {
      int ff = f, gg = g;
      f = Math.Max(nums[i], Math.Max(ff * nums[i], gg * nums[i]));
      g = Math.Min(nums[i], Math.Min(ff * nums[i], gg * nums[i]));
      ans = Math.Max(ans, f);
    }
    return ans;
  }
}