难度: Medium
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数运行时间: 24 ms
内存: 16.5 MB
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = max(nums)
multi = 1
for i in range(len(nums)):
if nums[i] == 0:
multi = 1
else:
multi = multi * nums[i]
ans = max(multi, ans)
multi = 1
for i in range(len(nums)-1, -1, -1):
if nums[i] == 0:
multi = 1
else:
multi = multi * nums[i]
ans = max(multi, ans)
return ans
这个题解采用了动态规划的思路。它从左到右遍历数组，用一个变量 multi 记录当前连续子数组的乘积，同时用 ans 记录遇到的最大乘积。当遇到 0 时，multi 会重置为 1。然后再从右到左遍历一遍数组，同样更新 multi 和 ans，最后返回 ans 即可得到乘积最大子数组的乘积。这样可以同时处理负数的情况。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = max(nums) # 初始化 ans 为数组中的最大值
multi = 1 # 初始化当前连续子数组的乘积为 1
# 从左到右遍历数组
for i in range(len(nums)):
if nums[i] == 0:
multi = 1 # 如果遇到 0，重置 multi 为 1
else:
multi = multi * nums[i] # 更新当前连续子数组的乘积
ans = max(multi, ans) # 更新最大乘积
multi = 1 # 重置 multi 为 1
# 从右到左遍历数组
for i in range(len(nums)-1, -1, -1):
if nums[i] == 0:
multi = 1 # 如果遇到 0，重置 multi 为 1
else:
multi = multi * nums[i] # 更新当前连续子数组的乘积
ans = max(multi, ans) # 更新最大乘积
return ans
这种方法能够有效处理包含负数的情况。因为连续子数组的乘积会因为负数的数量和位置而变化。例如，一个子数组包含偶数个负数可能在遍历到最后一个负数时达到最大乘积。但如果是奇数个负数，可能需要从另一端开始计算才能包含所有负数并达到最大乘积。通过从两个方向遍历数组，我们可以确保考虑到所有这些情况，从而找到真正的最大乘积。
重置 multi 为1的逻辑是基于0的特性。在乘积中，任何数与0相乘都会得到0，这意味着一旦遇到0，之前累积的乘积信息将不再有效，必须重新开始计算。因此，0的存在实际上会断开连续子数组，使之前的乘积结果失效，所以需要重置 multi 为1来重新开始新的连续子数组的乘积计算。
题解中已经通过初始化 ans 为数组中的最大值来考虑了单个元素可能是最大乘积的情况，这包括了0（当数组中所有元素为负数且0是非负的最大值时）。因此，在遇到0时重置乘积并不会忽视0可能是最优解的情况。实际上，这种处理确保了每段非零连续子数组的乘积被正确计算和比较。
在这个题解中，动态规划体现在通过一个迭代的乘积 multi 来连续计算子数组的乘积，并用 ans 记录遇到的最大值。每次迭代时，multi 会乘以当前的数组元素（除非遇到0，此时会重置），这样每个元素都会使用前一个元素的乘积结果（multi）来更新当前的最大乘积。这种方式允许每一步都建立在前一步的计算基础上，有效地使用之前的计算结果。