Maximum Product Subarray
将 nums 的一个子数组中的元素相乘，并返回任意子数组能够得到的最大乘积。子数组由连续元素组成，中间没有间隔，并且不能为空，因此即使数组中全是负数，也有答案。可以包含零和负数。
函数
- numsinteger-array
- 要相乘的整数，每个都在 -10 到 10 之间
- 返回值integer
- 非空子数组的最大乘积
约束条件
1 ≤ nums.length ≤ 2 × 104-10 ≤ nums[i] ≤ 10- 每个子数组的乘积都能放入 32 位有符号整数中。
示例
- 输入
- nums = [2, -5, 3, -2, 0, 4]
- 输出
- 60
- 解释
- 两个负数相乘会抵消负号：
2 × -5 × 3 × -2 = 60。0 把数组分成两部分，另一边的 4 无法超过 60。
- 输入
- nums = [-2, 3, -4, -1]
- 输出
- 24
- 解释
- 整个数组相乘的结果是 -24，因为其中有三个负数。去掉最后一个元素后，还剩两个负数：
-2 × 3 × -4 = 24，比去掉第一个元素得到的 12 更大。
- 输入
- nums = [-6, 0, -7]
- 输出
- 0
- 解释
- 不包含 0 的子数组是一个单独的负数，包含 0 的子数组乘积为 0。最好的选择是子数组
[0]。
进阶
如何在仍然保持 O(n) 时间复杂度和 O(1) 空间复杂度的情况下，同时报告最佳子数组的起始位置和结束位置？
提示
逐个打开提示，每个都会多透露一点。
对于求和，累计总和一旦低于 0，就不值得保留了。对于求积，一个很小的负数乘积在下一个负数出现时，可能立刻变成最大的乘积。除了目前为止的最大乘积，你还应该记录什么？
查看在当前位置结束的子数组。其中最大的乘积可能是当前数字本身，也可能是当前数字乘以前一个位置结束的最大乘积，或者是当前数字乘以前一个位置结束的最小乘积。
遍历数组时，维护
high和low，它们分别表示以当前索引结尾的子数组的最大乘积和最小乘积。对于每个新数字，先根据旧值计算两个候选乘积，然后更新这两个值，并记住你遇到过的最大high。
题解
乘以负数会反转乘积的顺序，因此目前最小的乘积下一步可能变成最大的乘积，而 0 会清除所有乘积。在每个索引处保留两个值，而不是一个：以该位置结尾的子数组的最大乘积和最小乘积，这样只需遍历一遍即可。
将每个起点开始的所有子数组相乘
结果正确，但无法在最大的测试中运行完毕
思路
固定起始索引，然后向右移动结束索引，将当前的 product 乘以每个新元素。每一步都将它与当前最佳值比较，这样就能遍历每个子数组一次。将 best 初始设为 nums[0]，因为答案可能是负数。
起始索引和结束索引大约有 n²/2 种组合，每种组合进行一次乘法：对于 20,000 个元素，需要 2 × 10^8 次乘法。
算法
- 将
best设为nums[0]。 - 对于每个
start，将product设为 1。 - 让
end从start移动到最后一个索引，并将product乘以nums[end]。 - 如果
product大于best，就保存它。 - 返回
best。
def maxProduct(nums):
n = len(nums)
best = nums[0]
for start in range(n):
product = 1
for end in range(start, n):
# product is now the product of nums[start..end]
product *= nums[end]
if product > best:
best = product
return best从两端扫描，遇到零时重新开始
思路
零会把数组分成不含零的连续段。在每一段中，每个值的绝对值都至少为 1，因此更长的子数组绝对值乘积不会更小，只有符号会变化。负数个数为偶数时，整段就是最佳选择。负数个数为奇数时，必须去掉一个负数，最佳切法是去掉第一个负数及其之前的所有元素，或者去掉最后一个负数及其之后的所有元素。无论哪种情况，保留的都是这段的后缀或前缀。
从左向右遍历时，用一个不断更新的乘积检查每个前缀，并在遇到 0 后将乘积重置为 1。从右向左遍历时，检查每个后缀。对于 [-2, 3, -4, -1]，从左向右遍历会依次得到 -2、-6、24 和 -24，从右向左遍历会依次得到 -1、4、12 和 -24，因此答案是 24。这个论证要求每个非零值的绝对值都至少为 1，对于整数来说，这个条件成立。
算法
- 将
best设为nums[0]，并将product设为 1。 - 从左向右遍历：将
product乘以每个元素，并保留best和product中较大的值。 - 每当
product变为 0 时，就将它重新设为 1，让下一轮从头开始。 - 再次将
product设为 1，并从右向左进行相同的遍历。 - 返回
best。
def maxProduct(nums):
best = nums[0]
# Left to right: the product of every prefix of each zero-free run
product = 1
for num in nums:
product *= num
best = max(best, product)
if product == 0:
product = 1 # a zero ends the run, the next one starts fresh
# Right to left: the product of every suffix of each zero-free run
product = 1
for num in reversed(nums):
product *= num
best = max(best, product)
if product == 0:
product = 1
return best记录以此处结尾的最大和最小乘积
思路
每个以索引 i 结尾的子数组，要么只有 nums[i]，要么是 nums[i] 乘以一个以 i-1 结尾的子数组。当 nums[i] 为负数时，这些乘积中最大的乘积来自以 i-1 结尾的最小乘积。因此要同时保留两者：以当前索引结尾的子数组的最大乘积 high 和最小乘积 low。新的 high 是 num、high × num 和 low × num 中的最大值，新的 low 则是其中的最小值。单独取 num，就能在遇到 0 后重新开始这一段。
在第一个示例中，遇到 -2 时，low 是 -30，而 -30 × -2 = 60 会成为 high，也就是答案。
算法
- 将
high、low和best设为nums[0]。 - 对于后续的每个元素
num，计算a = high × num和b = low × num。 - 将
high设为num、a和b中最大的值，将low设为其中最小的值。 - 将
best设为best和high中较大的值。 - 返回
best。
def maxProduct(nums):
# high and low: the largest and smallest product of a subarray ending at the current index
high = low = best = nums[0]
for num in nums[1:]:
# Multiply both old values first: a negative num swaps their roles
a = high * num
b = low * num
high = max(num, a, b)
low = min(num, a, b)
best = max(best, high)
return best
易错点和边界情况
- 只跟踪最大的乘积。第一个示例会返回 4，而不是 60，因为它丢掉了 -30，而 -2 会将其变成 60。
- 用已经更新的
high计算新的low。在更改任一变量之前，先保存high × num和low × num。 - 将
best初始设为 0 或 1。[-3]必须返回 -3，因为子数组不能为空。 - 只运行双向遍历法中的左侧遍历。对于
[-2, 3, 4]，它看到的最大值也只有 -2，但后缀[3, 4]的乘积是 12。 - 在 JavaScript、TypeScript 和 Lua 中，0 乘以负数会得到
-0，打印时会带有负号。返回结果前先加上 0。
常见问题3
最大乘积子数组的时间复杂度是多少？
跟踪以每个索引结尾的最大和最小乘积需要 O(n) 时间和 O(1) 空间。两遍前缀和后缀方法的开销相同。从每个起点计算所有子数组的乘积需要 O(n²) 时间。
为什么“最大乘积子数组”需要取最小乘积？
负数会把以此前位置结尾的最小乘积变成最大的乘积。只保留最大乘积的话，等需要这个候选值时，它就不见了。在 [3, -2, -4] 中，-4 之前的最小乘积是 -6，而 -6 × -4 = 24 就是答案。
最大乘积子数组与最大子数组有什么不同？
对于求和，负的累计总和只会造成负面影响，因此每个索引只需要一个值。对于求积，遇到另一个负数后，负的累计值可能变成最大值，而零会将所有值重置。因此，求积版本会在每个索引处记录最大乘积和最小乘积。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def maxProduct(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, -5, 3, -2, 0, 4]
预期输出
60