题目定位
Kadane 算法本质上就是一个极简 DP：当前位置是继续接上前面的子数组更优，还是从自己重新开始更优。
关键观察
每个位置只需要知道“以这里结尾的最佳子数组”，并不需要保留所有历史区间。
目标复杂度
O(n) / O(1)
这题的解法思路怎么拆
1
Kadane 算法本质上就是一个极简 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
把全局最优和局部 ending-here 状态混在一起。
高频追问
如果还要返回子数组区间，怎么记录？
如果数组是环形的，思路有什么变化？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。