LeetCode 152：乘积最大子数组，从负数反例推导双状态动态规划
题目要求 给定整数数组 nums，找到一个乘积最大的非空连续子数组，返回这个最大乘积。 “连续”意味着选中的元素必须挨在一起，不能跳过中间的数；“非空”意味着至少选一个元素。只需返回乘积，不需要返回区间或区间长度。 输入：nums = [2, 3, -2, 4] 输出：6 解释：连续子数组 [2, 3] 的乘积最大，为 2 * 3 = 6。 输入：nums = [-2, 0, -1] 输出：0 解释：不能跳过 0，把 -2 和 -1 当作一个子数组；选择 [0] 可得到 0。 约束为 1 <= len(nums) <= 20000、-10 <= nums[i] <= 10。题目保证任意子数组的乘积都在 32 位有符号整数范围内。输入不会为空，但可能包含负数和零。 第 1 步：先枚举每个非空连续区间 对 [2, 3, -2, 4]，如果直接把整个数组乘起来，得到的是 -48，而答案是前两个元素的乘积 6。因此，当前“把所有元素相乘”的做法缺少真正需要做的选择：从哪里开始，到哪里结束。 先不尝试猜哪个区间更好。最直接的正确办法，是枚举每一个合法区间，计算乘积，再保留最大的值。 固定左端点 left 后，让右端点 right 逐个向右移动。原来区间的乘积只需再乘上新加入的 nums[right]，就能得到扩展后区间的乘积。这样每次扩展不必从头乘一遍。 加入这个完整的枚举函数： def max_product_bruteforce(nums: list[int]) -> int: answer = nums[0] for left in range(len(nums)): product = 1 for right in range(left, len(nums)): product *= nums[right] answer = max(answer, product) return answer 这里有两个不同的初始化： ...