题目定位
和求和 DP 不同，乘积 DP 必须同时维护当前位置结尾的最大值和最小值，因为负数会立刻交换它们的角色。
关键观察
当前这个负数可能会把之前的最小值直接翻成新的最大值。
目标复杂度
O(n) / O(1)
这题的解法思路怎么拆
1
和求和 DP 不同，乘积 DP 必须同时维护当前位置结尾的最大值和最小值，因为负数会立刻交换它们的角色。
2
当前这个负数可能会把之前的最小值直接翻成新的最大值。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
只维护当前最大值，丢掉负数翻转信息。
warning
先更新 max 再更新 min，导致滚动状态被污染。
高频追问
为什么只要有负数，就必须保留两个状态？
0 在这道题里为什么等于把问题切成多段？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。