GFG最大乘积子数组Python代码调试求助（DSA练习）

给定包含N个整数（可正、可负、可为零）的数组Arr[]，需求解最大乘积子数组的乘积。以下是我编写的暴力枚举代码，但无法通过所有测试用例（或超时），请帮忙检查并修正：

def maxSubarrayProduct(arr, n):
  
        result = arr[0]
  
        for i in range(n):
      
            mul = arr[i]
        
            for j in range(i + 1, n):
          
                result = max(result, mul)
                mul *= arr[j]
          
            result = max(result, mul)
      
        return result

代码问题分析 #

你的暴力枚举思路逻辑上能覆盖大部分情况，但时间复杂度为O(n²)，当数组长度较大时会触发超时，无法通过GFG的大规模测试用例，且效率极低，不是该问题的最优解法。

最优修正方案 #

利用乘积的特性：负数相乘可能得到正数，因此需要同时跟踪当前的最大乘积和最小乘积（最小乘积乘以负数可能转化为最大乘积）。以下是O(n)时间复杂度、O(1)空间复杂度的实现：

def maxSubarrayProduct(arr, n):
    if n == 0:
        return 0
    
    curr_max = curr_min = result = arr[0]
    
    for i in range(1, n):
        # 当前元素为负时，交换最大和最小乘积（负数会反转乘积的大小关系）
        if arr[i] < 0:
            curr_max, curr_min = curr_min, curr_max
        
        # 更新当前最大/最小乘积：要么重新开始子数组，要么延续之前的乘积
        curr_max = max(arr[i], curr_max * arr[i])
        curr_min = min(arr[i], curr_min * arr[i])
        
        # 更新全局最大结果
        result = max(result, curr_max)
    
    return result

逻辑说明 #

• 初始化curr_max、curr_min和result为数组第一个元素，确保单元素数组的正确性。
• 遍历到负数时交换最大/最小乘积：负数会让原本的最大乘积变最小，最小乘积变最大，必须交换才能正确计算后续乘积。
• 更新curr_max和curr_min：每次迭代有两种选择——以当前元素作为新子数组的起点，或者将当前元素加入之前的子数组。
• 实时更新全局最大结果，确保不会遗漏任何可能的子数组乘积。

该方案能正确处理所有边界情况：

• 全负数数组：自动选中乘积最大的偶数个负数组合。
• 包含零的数组：零会中断当前子数组，后续自动从非零元素重新计算。
• 正负交替的数组：通过跟踪最小乘积，能捕捉到负负得正的最大乘积。

内容的提问来源于stack exchange，提问作者Ahmed Dulap