如何用Python高效解决最大乘积子数组（Maximum Product Subarray）问题

问题回顾 #

给定一个包含正数、负数或零的整数数组，找出任意连续子数组的最大乘积。

示例：

• 输入：[-2, 6, -3, -10, 0, 2]
• 输出：180
• 解释：子数组 [6, -3, -10] 的乘积为 6 * -3 * -10 = 180。

你尝试的代码框架：

def maxProduct(arr):
   max_ending_here = 0
   min_ending_here = 0
   max_so_far = 0

# Not sure how to update max_ending_here and min_ending_here for negative numbers
    for num in arr:
        pass  # Implementation goes here

 return max_so_far

针对你的问题的解答 #

1. 负数与零的状态转换处理 #

核心逻辑是：负数会反转乘积的大小关系（最大变最小，最小变最大），零会中断连续子数组的乘积链。具体处理方式如下：

• 初始值修正：不能把max_ending_here、min_ending_here、max_so_far初始化为0，否则会漏掉全负数数组的情况（比如[-2,-3]的最大乘积是6），应该初始化为数组的第一个元素。
• 遍历过程的状态更新：
  每次遍历到当前数字时，先保存当前的max_ending_here副本（因为更新最小值时会用到原始的最大值），然后同时计算新的最大、最小乘积：
  • 新的max_ending_here取三个值的最大值：当前数字本身、当前数字乘之前的最大乘积、当前数字乘之前的最小乘积（负负得正可能得到更大值）
  • 新的min_ending_here取三个值的最小值：当前数字本身、当前数字乘之前的最大乘积（大正数乘负数会得到很小的值）、当前数字乘之前的最小乘积
  • 遇到零时，上述逻辑会自动重置状态（比如当前数字是0，乘之前的任何数都是0，此时max_ending_here会取0和当前数字0的最大值，后续遍历会从下一个数重新开始计算连续子数组）

2. 避免O(n²)复杂度的方法 #

你尝试的跟踪当前最大/最小乘积的思路就是最优的线性解法，完全不需要枚举所有子数组。这种方法只需要遍历数组一次，每个元素的处理都是O(1)操作，时间复杂度远低于O(n²)。

3. 最优时间复杂度及保证 #

该问题的最优时间复杂度是O(n)，因为要确定最大乘积，必须遍历数组中所有元素一次（无法跳过任何元素）。要确保达到这个复杂度，只需保证遍历过程中没有嵌套循环，每个元素的处理仅包含常数次的比较、乘法操作即可。

修正后的完整代码 #

def maxProduct(arr):
    if not arr:
        return 0
    
    # 初始化状态为数组第一个元素，适配全负数场景
    max_ending_here = min_ending_here = max_so_far = arr[0]
    
    for num in arr[1:]:
        # 保存当前max_ending_here，避免更新时被覆盖
        temp_max = max_ending_here
        # 计算新的当前最大乘积
        max_ending_here = max(num, max_ending_here * num, min_ending_here * num)
        # 计算新的当前最小乘积
        min_ending_here = min(num, temp_max * num, min_ending_here * num)
        # 更新全局最大乘积
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
    
    return max_so_far

内容的提问来源于stack exchange，提问作者Rishal kumar