最大子段和

给一串可正可负的数，求连续一段的最大和。比如 2 -1 3 的答案是 4（整段 2+(-1)+3）。

定义状态

设 dp[i] = 以第 i 个数结尾的最大连续和。"以 i 结尾"是关键——它保证选出的这一段是连续的。

转移：要么接上，要么另起

到第 $i$ 个数，只有两个选择：

• 接在前面那段后面：$d{p}_{i-1}+a_i$
• 自己另起一段：$a_i$（当前面那段是负数、只会拖后腿时）

取较大者：

$$d{p}_i=\max \left(a_i,d{p}_{i-1}+a_i\right)$$

答案是所有 $d{p}_i$ 里的最大值——因为事先不知道最优段在哪结尾。

int best=a[0], dp=a[0];
for(int i=1;i<n;i++){
    dp = max(a[i], dp + a[i]);
    best = max(best, dp);
}
// best 即答案，复杂度 O(n)

这个"以 $i$ 结尾"的设状态套路，在 DP 里会一再出现，务必吃透。