Kadane算法
类型：算法
用途：求一个数组的最大子数组元素和
基本思路
遍历数组，同时维护两个变量：
current_sum：以当前元素结尾的最大子数组和max_sum：全局最大子数组和
二者均初始化为数组的第一个元素。
核心操作
每移动到一个新元素 x 时：
current_sum可以选择：- 将
x与之前的子数组连接（current_sum + x） - 从
x重新开始（x）
- 将
- 选择两者中较大的值作为新的
current_sum
这样做的原因是：如果之前的子数组和为负，加上它只会让总和更小，不如直接舍弃。
更新完 current_sum 后，再与 max_sum 比较，取较大者作为新的 max_sum。
正确性保证
- 确保先前子数组的总和始终为正（若为负则舍弃）
- 即使所有元素都是负数，也能选出最大的负数（即负得最少的那一个）
示例题目
本题可用 Kadane 算法的变体求解（最大子数组差）。