连续子数组的最大乘积
字数 1949 2025-10-29 11:32:03

连续子数组的最大乘积

题目描述
给定一个整数数组nums（可能包含负数），请你找出数组中乘积最大的连续子数组（该子数组至少包含一个数字），并返回该子数组的乘积。

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

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是连续子数组。实际上，任何包含0或单独[-1]的乘积都小于等于0，最大乘积子数组是 [0]，乘积为0。

解题过程

这个问题与最大子序和类似，但关键区别在于乘积运算中负负得正的特性。一个负数乘以另一个负数可能变成正数，并且可能成为最大乘积。因此，我们不能只维护一个最大值状态。

  1. 状态定义
    我们需要两个动态规划数组：

    • maxDP[i]：表示以第i个元素结尾的连续子数组的最大乘积。
    • minDP[i]：表示以第i个元素结尾的连续子数组的最小乘积。

    为什么需要最小值？因为如果nums[i]是一个负数，那么乘以一个很小的负数（minDP[i-1]）可能会得到一个很大的正数。

  2. 状态转移方程
    对于每个位置i，我们有三种选择：

    • 自己单独成为一个子数组：nums[i]
    • 将nums[i]与以i-1结尾的最大乘积子数组连接：nums[i] * maxDP[i-1]
    • 将nums[i]与以i-1结尾的最小乘积子数组连接：nums[i] * minDP[i-1]（当nums[i]和minDP[i-1]都是负数时，乘积可能很大）

    因此，状态转移方程为：
    maxDP[i] = max( nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1] )
    minDP[i] = min( nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1] )

    最终，整个数组的最大乘积就是所有maxDP[i]中的最大值。

  3. 初始化
    对于第一个元素（i=0）：
    maxDP[0] = nums[0]
    minDP[0] = nums[0]
    因为只有一个元素的子数组，其最大和最小乘积都是它本身。

  4. 计算步骤（以示例 nums = [2, 3, -2, 4] 为例）

    • i = 0:
      maxDP[0] = 2
      minDP[0] = 2
      当前全局最大值 globalMax = 2

    • i = 1:
      候选1: nums[1] = 3
      候选2: nums[1] * maxDP[0] = 3 * 2 = 6
      候选3: nums[1] * minDP[0] = 3 * 2 = 6
      maxDP[1] = max(3, 6, 6) = 6
      minDP[1] = min(3, 6, 6) = 3
      globalMax = max(globalMax, maxDP[1]) = max(2, 6) = 6

    • i = 2:
      候选1: nums[2] = -2
      候选2: nums[2] * maxDP[1] = -2 * 6 = -12
      候选3: nums[2] * minDP[1] = -2 * 3 = -6
      maxDP[2] = max(-2, -12, -6) = -2
      minDP[2] = min(-2, -12, -6) = -12
      globalMax = max(6, -2) = 6 (保持不变)

    • i = 3:
      候选1: nums[3] = 4
      候选2: nums[3] * maxDP[2] = 4 * (-2) = -8
      候选3: nums[3] * minDP[2] = 4 * (-12) = -48
      maxDP[3] = max(4, -8, -48) = 4
      minDP[3] = min(4, -8, -48) = -48
      globalMax = max(6, 4) = 6

    最终结果为6。

  5. 空间优化
    由于maxDP[i]和minDP[i]只依赖于前一个状态maxDP[i-1]和minDP[i-1]，我们可以只用两个变量currentMax和currentMin来滚动更新，而不需要整个数组，将空间复杂度从O(n)降低到O(1)。

关键点总结

  • 核心思想是同时维护以当前元素结尾的最大乘积和最小乘积两个状态。
  • 因为负数的存在，当前的最大乘积可能由之前的最小乘积（一个很小的负数）乘以当前负数得到。
  • 状态转移时，需要比较三种可能性：当前元素本身、当前元素乘以前一个最大乘积、当前元素乘以前一个最小乘积。
连续子数组的最大乘积 题目描述 给定一个整数数组nums（可能包含负数），请你找出数组中乘积最大的连续子数组（该子数组至少包含一个数字），并返回该子数组的乘积。 示例 1: 输入: [ 2,3,-2,4 ] 输出: 6 解释: 子数组 [ 2,3 ] 有最大乘积 6。 示例 2: 输入: [ -2,0,-1 ] 输出: 0 解释: 结果不能为 2, 因为 [ -2,-1] 不是连续子数组。实际上，任何包含0或单独[ -1]的乘积都小于等于0，最大乘积子数组是 [ 0 ]，乘积为0。 解题过程 这个问题与最大子序和类似，但关键区别在于乘积运算中负负得正的特性。一个负数乘以另一个负数可能变成正数，并且可能成为最大乘积。因此，我们不能只维护一个最大值状态。 状态定义 我们需要两个动态规划数组： maxDP[i] ：表示以第i个元素结尾的连续子数组的最大乘积。 minDP[i] ：表示以第i个元素结尾的连续子数组的最小乘积。 为什么需要最小值？因为如果 nums[i] 是一个负数，那么乘以一个很小的负数（ minDP[i-1] ）可能会得到一个很大的正数。 状态转移方程 对于每个位置i，我们有三种选择： 自己单独成为一个子数组： nums[i] 将 nums[i] 与以 i-1 结尾的最大乘积子数组连接： nums[i] * maxDP[i-1] 将 nums[i] 与以 i-1 结尾的最小乘积子数组连接： nums[i] * minDP[i-1] （当 nums[i] 和 minDP[i-1] 都是负数时，乘积可能很大） 因此，状态转移方程为： maxDP[i] = max( nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1] ) minDP[i] = min( nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1] ) 最终，整个数组的 最大乘积 就是所有 maxDP[i] 中的最大值。 初始化 对于第一个元素（i=0）： maxDP[0] = nums[0] minDP[0] = nums[0] 因为只有一个元素的子数组，其最大和最小乘积都是它本身。 计算步骤（以示例 nums = [ 2, 3, -2, 4] 为例） i = 0: maxDP[0] = 2 minDP[0] = 2 当前全局最大值 globalMax = 2 i = 1: 候选1: nums[1] = 3 候选2: nums[1] * maxDP[0] = 3 * 2 = 6 候选3: nums[1] * minDP[0] = 3 * 2 = 6 maxDP[1] = max(3, 6, 6) = 6 minDP[1] = min(3, 6, 6) = 3 globalMax = max(globalMax, maxDP[1]) = max(2, 6) = 6 i = 2: 候选1: nums[2] = -2 候选2: nums[2] * maxDP[1] = -2 * 6 = -12 候选3: nums[2] * minDP[1] = -2 * 3 = -6 maxDP[2] = max(-2, -12, -6) = -2 minDP[2] = min(-2, -12, -6) = -12 globalMax = max(6, -2) = 6 (保持不变) i = 3: 候选1: nums[3] = 4 候选2: nums[3] * maxDP[2] = 4 * (-2) = -8 候选3: nums[3] * minDP[2] = 4 * (-12) = -48 maxDP[3] = max(4, -8, -48) = 4 minDP[3] = min(4, -8, -48) = -48 globalMax = max(6, 4) = 6 最终结果为6。 空间优化 由于 maxDP[i] 和 minDP[i] 只依赖于前一个状态 maxDP[i-1] 和 minDP[i-1] ，我们可以只用两个变量 currentMax 和 currentMin 来滚动更新，而不需要整个数组，将空间复杂度从O(n)降低到O(1)。 关键点总结 核心思想是同时维护以当前元素结尾的 最大乘积 和 最小乘积 两个状态。 因为负数的存在，当前的最大乘积可能由之前的最小乘积（一个很小的负数）乘以当前负数得到。 状态转移时，需要比较三种可能性：当前元素本身、当前元素乘以前一个最大乘积、当前元素乘以前一个最小乘积。