状态怎么定

状态定义决定了后面所有推导的难易。好的状态要满足"无后效性"——一旦确定，将来的决策只看当前状态，不用回头翻历史。拿卡片上的问题说：定成"前 $i$ 个数里的最大连续和"，你会发现推 $f[i]$ 时不知道前面那段有没有连到第 $i$ 个，接不上；定成"以第 $i$ 个数结尾的最大连续和"，结尾被钉死了，第 $i$ 个要么接前面、要么单独重开，转移一下就写出来。经验：把某个"结尾/位置/最后一步"固定进状态，往往能让转移变清晰。

$$f[i]=\max (f[i-1]+a[i],a[i])$$

int f = a[0], ans = a[0];
for (int i = 1; i < n; i++) {
    f = max(f + a[i], a[i]);
    ans = max(ans, f);
}

注意最终答案是所有 $f[i]$ 的最大值，而不是 $f[n-1]$——这是最常见的错。定错状态的信号是：转移时总要"再回头看一眼前面选没选"，说明信息没进状态。