Kadane 算法

Kadane算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成动态规划的一个例子。

令 dp[j] 为以 A[j] 结尾的最大子段和。也就是，

\[\text{dp}[j] = \max\limits_i (A[i] + A[i+1] + \cdots + A[j])\]

那么，以 j+1 结尾的子段（例如 A[i], A[i+1] + ... + A[j+1]）最大化了 A[i] + ... + A[j] 的和，当这个子段非空那么就等于 dp[j] 否则就等于 0。所以，有以下递推式： \(\(\text{dp}[j+1] = A[j+1] + \max(\text{dp}[j], 0)\)\) 由于一个子段一定从某个位置截止，所以 \(\max\limits_j dp[j]\) 就是需要的答案。

Kadane 算法通常以节约空间复杂度的形式表示。我们只维护两个变量 ans 等于 \(\max\limits_j dp[j]\) 和 cur 等于 \(dp[j]\)。随着 j 从 \(0\) 到 \(A.\text{length}-1\) 遍历。