最大子段和

一句话理解

最大子段和：一段连续子数组的最大和。

为什么要学

Kadane：扫一遍。

讲解

cur=max(a[i], cur+a[i])，ans=max(ans,cur)。全负时 ans 应是最大的那个负数（看题目）。

例子

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

当前段要么接上，要么从 i 重开。

常见错误

• 初值 0 但全负。
• 不连续当连续。