0152 - Maximum Product Subarray
题干
破题
经典 Medium 但是 Hard ，这道题单独看可以算作 Medium 类型的题目，但是作为 DP 标签就显得很 Hard，因为题目和一般的 DP 思路好像有关系，实质是没有关系，如果再类比 0053 - Maximum Subarray 的思路那就更困难了，难就难在干扰项。
同样也是正、负、零三种整数，而累积和累和的区别在于累积的符号会翻转而且幅度越来越大，最大数可以由正数乘积得到，或者负数的乘积遇到负数翻而来。
解①常规：
用 $0$ 把数组分段，按照负数的数量分情况讨论：
$=0$：直接累乘
$=1$：比较两边的正数的累积结果，
$=2$：直接累积
$\geqslant$ 3：
3.1. 奇数，比较从第一个负数后的正数开始乘到尾和从头开始乘到最后一个负数前的正数；
3.2. 偶数，累乘
这样只需要记录负数的坐标（不需要记全，对于超过了两个的，只需要记录第一个和最后一个负数的坐标即可）。
from typing import List
from functools import reduce
from operator import mul
def solve(nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
neg = []
zero = -1
ans = 0
nums.append(0)
for i in range(len(nums)):
if nums[i] < 0:
if len(neg) == 2:
neg[-1] = i
else:
neg.append(i)
elif nums[i] == 0:
if i-zero < 2:
cand = 0
elif i-zero == 2:
cand = nums[i-1]
else: # i-zero > 2
if len(neg) % 2 == 0:
cand = reduce(mul, nums[zero+1:i])
elif len(neg) == 1:
if nums[zero+1:neg[0]]:
cand1 = reduce(mul, nums[zero+1:neg[0]])
else:
cand1 = 0
if nums[neg[0]+1:i]:
cand2 = reduce(mul, nums[neg[0]+1:i])
else:
cand2 = 0
cand = max(cand1, cand2)
else:
cand1 = reduce(mul, nums[zero+1:neg[-1]])
cand2 = reduce(mul, nums[neg[0]+1:i])
cand = max(cand1, cand2)
zero = i
neg.clear()
if ans < cand:
ans = cand
return ans
运行时间：76 ms (beats 78.56%, ~100%)，内存占用：16.2 MB (beats 99.98%)。
解②正负值：
可以在一遍的过程中计算这些数，只需要两个变量来存储状态，pos 表示最大的正数，neg 表示最小的负数（或者绝对值最大的负数。
这两个变量代表的子数组拥有相同的后缀，也就是扫描到的位置。
在开始或者遇到 $0$ 时，pos 和 neg 都设为 None，如果在 None 的时候遇到同符号的数值时，赋值给它们，否则就继续累乘；如果不为 None 则当遇到反符号的时候，就给反符号赋值（注意保存被覆盖的值，这时分组赋值就很合适）
def solve(nums: List[int]) -> int:
pos = neg = None
ans = nums[0]
for v in nums:
if v > 0:
if pos is not None:
pos *= v
else:
pos = v
if neg is not None:
neg *= v
if pos > ans:
ans = pos
elif v == 0:
if ans < 0:
ans = 0
pos = neg = None
else:
if neg is None:
if pos is None:
neg = v
else:
pos, neg = None, pos * v
else:
if pos is None:
pos, neg = neg * v, v
else:
pos, neg = neg * v, pos * v
if pos > ans:
ans = pos
return ans
运行时间：73 ms (beats 88.24%, ~100%), 内存占用：16.95 MB (~100%)。
解③前后缀：
由于实际上的差异只是由，也可以不考虑正负值的变化情况，直接从前缀和后缀两个方向计算累乘，当发现累积归为 0 时，就改乘为赋值。
from typing import List
def solve(nums: List[int]) -> int:
prefix = postfix = 0
ans = nums[0]
for i in range(len(nums)):
if prefix == 0:
prefix = nums[i]
else:
prefix *= nums[i]
if postfix == 0:
postfix = nums[~i]
else:
postfix *= nums[~i]
ans = max(ans, prefix, postfix)
return ans
运行时间：80 ms (beats 54.67%, ~100%)，内存占用：16.76 MB (~100%)。
注解
