LeetCode 152:最大乘积子数组代码错误排查——返回1而非预期6

你的代码核心问题 #

1. 递归终止条件错误：当i < 0时返回1，这会导致递归到最底层时，所有分支的最终比较基准都是1，完全忽略了实际的子数组乘积值。比如处理到数组第一个元素时，计算出的rs是2，但递归调用func(nums, -1, rs)返回1，导致后续比较都以1为基准，漏掉了真实的乘积。

2. 未将当前乘积纳入最大值比较：你的递归逻辑只比较了两个递归分支的结果，却没有把当前计算的rs（即以当前元素结尾的连续子数组乘积）加入到最大值的判断中。例如处理元素3时，rs=2*3=6，但代码里没有把这个6和后续递归结果比较，直接取两个递归的返回值（最终都是1），导致正确的乘积被丢弃。

3. 递归分支逻辑偏差：第二个递归分支func(nums,i-1,rs=1)的意图是“从当前元素重新开始”，但这个分支实际是去计算前i-1个元素的结果，和当前元素无关，完全偏离了“以当前元素为起点”的逻辑。

修正后的递归思路 #

递归过程中需要跟踪两个关键值：

• 以当前元素结尾的最大连续乘积（负数可能让之前的最小乘积变成最大）
• 遍历过程中的全局最大乘积

让递归函数返回三个值：以当前索引i结尾的最大乘积、最小乘积，以及到当前位置为止的全局最大乘积。

修正后的代码 #

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        def func(i):
            if i == 0:
                # 第一个元素，以它结尾的最大、最小乘积都是它本身，全局最大也是它
                return nums[i], nums[i], nums[i]
            prev_max, prev_min, global_max = func(i-1)
            # 以当前元素结尾的三种可能：单独当前元素、当前*前序最大、当前*前序最小（负数相乘转正）
            curr_max = max(nums[i], nums[i] * prev_max, nums[i] * prev_min)
            curr_min = min(nums[i], nums[i] * prev_max, nums[i] * prev_min)
            # 更新全局最大
            new_global_max = max(global_max, curr_max)
            return curr_max, curr_min, new_global_max
        
        _, _, result = func(len(nums)-1)
        return result

x=Solution()
print(x.maxProduct([2,3,-2,4]))  # 输出6

代码说明 #

• 递归终止在i=0，直接返回第一个元素的三个值（自身、自身、自身）
• 对于每个后续元素，计算以它结尾的最大/最小乘积：考虑单独取当前元素、和前序最大乘积相乘、和前序最小乘积相乘（因为负数乘负数会变大）
• 每次递归都更新全局最大乘积，最终返回全局最大值

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