给你一个整数数组 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] <= 10 nums 的任何子数组的乘积都 保证 是一个 32-位 整数
152.乘积最大子数组
给你一个整数数组 nums，请你找出其中乘积最大的 连续子数组，并返回该子数组的乘积值。
一、思路解析
和「最大子序和」(Maximum Subarray) 类似，但由于乘积会受到负数的影响（负负得正），同时还可能受到 0 的影响，需要特殊处理。因此，我们在遍历数组时，需要同时记录以下信息：
- 当前最大乘积（
max_prod） - 当前最小乘积（
min_prod）
之所以需要最小乘积，是因为如果当前数是负数，那么与之前的最小乘积相乘反而可能得到一个更大的乘积。
假设遍历数组时使用索引 i，则 max_prod[i] 和 min_prod[i] 的递推关系为：
- 如果
nums[i]≥ 0：max_prod[i] = max(nums[i], max_prod[i-1] * nums[i])min_prod[i] = min(nums[i], min_prod[i-1] * nums[i])
- 如果
nums[i]< 0：max_prod[i] = max(nums[i], min_prod[i-1] * nums[i])min_prod[i] = min(nums[i], max_prod[i-1] * nums[i])
也就是说，每次都要比较“只保留自己”(nums[i])和“与之前的最大/最小乘积相乘”两种情况，取其中对当前 max_prod 和 min_prod 最有利的结果。
遍历过程中，实时更新一个全局变量 res，记录迄今为止出现过的最大乘积。
复杂度分析：
- 时间复杂度：O(n)，只需要遍历一次数组。
- 空间复杂度：O(1)，只用几个临时变量即可完成，不需要额外的数组空间。
二、代码示例 (Python)
def max_product_subarray(nums):# 初始化max_prod = nums[0]min_prod = nums[0]res = nums[0]# 从第二个元素开始遍历for i in range(1, len(nums)):cur = nums[i]if cur < 0:# 交换 max_prod 和 min_prodmax_prod, min_prod = min_prod, max_prod# 更新 max_prod 和 min_prodmax_prod = max(cur, max_prod * cur)min_prod = min(cur, min_prod * cur)# 更新结果res = max(res, max_prod)return res
• 当 nums[i] 为正数时，与当前的最大乘积相乘会使结果变大；与当前最小乘积相乘只会让结果更小，故更新 max_prod 时取 max(cur, max_prodcur)，更新 min_prod 时取 min(cur, min_prodcur)。
• 当 nums[i] 为负数时，它与最小乘积相乘反而可能变成最大乘积，所以要先交换 max_prod 和 min_prod，再进行乘法比较。
• 若遇到 0，会将乘积归零，相当于“重新开始”计算，这在上述公式中也会自动得到正确的处理：max_prod 和 min_prod 都会与当前值（0）进行比较并被重置。
