最大子数组和：接上旧段还是从自己开张
子数组必须连续。走到每个数只问一次：前面那截和是正的就接着累，是负的就丢掉重开。历史最好另记一本。
current = max(nums[i], current + nums[i]) 表示以 i 结尾的最大子数组和；best 记录所有 current 的最大值。current 为负时接上去只会拖累未来，安全丢弃。时间 O(n)，空间 O(1)。
给你一个整数数组，找出一段连续、非空的子数组，使里面的数加起来最大，返回这个和。子数组必须挨在一起，中间不能挖空；至少要有一个数，不能交白卷。
主例 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]。连续一段 [4, -1, 2, 1] 的和是 6，这就是答案。注意 -1 被两边的正数托住，整段仍然比单独的 4 更大——负数不一定该切掉。
暴力枚举所有起点和终点能做对，但每一段都从头加，是平方级比较。本文要回答：为什么只要问「以当前数结尾的最好连续和」，以及主例里那次重启、那次留下负数，分别发生在哪一步。
current 管当前结尾，best 管历史冠军
第一直觉是枚举所有起点和终点，把每一段都加一遍。主例长度 9，大约 45 段。结果能对，但每一段的和都是从头重算。还有两种错觉更糟：只加正数，主例里 1+4+2+1+4=12，那不是子数组；看见负数就立刻切断，走到 4 后面的 -1 时一切断，后面的 2、1 接不上，最好成绩停在 4，小于 6。
缺的不是「哪一段最大」这张最终成绩单，而是一个可以递推的小问题：走到下标 i 时，以 nums[i] 结尾的连续段，最好能到多少。子数组必须连续，当前这个数要么接在前一段后面，要么自己当新段开头，没有第三种接法。一旦问题收成「以 i 结尾」，下一个位置只看前一个答案，不必回头重扫。
用两个变量记账。current 是「以当前数结尾的最好连续和」，best 是「到目前为止见过的最好连续和」。先用第一个数垫上：current = nums[0]，best = nums[0]。从第二个数开始，对每个 x 只问一句：current + x 和 x 谁更大。前者是带上前面那截，后者是从自己重新开张。取较大的作为新的 current，再拿它去挑战 best。
current + x 和 x 比大小，两边同时减掉 x，不等式变成 current 和 0 比。前面那截和大于 0，带上它；小于等于 0，丢掉它。切断看的是「前面和是不是累赘」，不是「当前是不是负数」。主例下标 3 的 4 选择开张，因为当时 current 是 -2；下标 4 的 -1 选择留下，因为当时 current 是 4。把决策说成「当前是不是负数」会在 -1 上切错。
用手走主例。i=0，只有 -2，current=-2，best=-2。i=1 读到 1：-2+1=-1，单独的 1 更大，重启，best 升到 1。i=2 读到 -3：1+(-3)=-2，比单独 -3 亏得少，current=-2，best 仍是 1。i=3 读到 4：-2+4=2，单独的 4 更大，从 4 开张，best=4。演示场景里这一步的区间缩回 [3,3]，正是「负前缀被丢掉」。
i=4 读到 -1：4+(-1)=3，比单独 -1 强，延伸，current=3，best 仍是 4。-1 没有切断这段。i=5 读到 2：3+2=5，刷新 best。i=6 读到 1：5+1=6，best=6，对应区间 [4,-1,2,1]。i=7 读到 -5：6-5=1，current 掉到 1，best 锁在 6。i=8 读到 4：1+4=5，打不过已经记下的 6。答案停在 6。
全是负数时这套决策仍然成立。[-3,-1,-2] 里每一次都是「自己开张」赢过「带上前面」，best 停在 -1，也就是最大的那个负数。题目要求子数组非空，不能返回 0。所以必须用 nums[0] 初始化，不能把 best 垫成 0。
为什么丢弃负前缀安全若 current < 0，把它接在任何一个未来子数组前都会让总和变小，因此最优解必不包含它。丢掉的是「已经变成累赘的前缀」，不是「凡是负数」。主例里的 -1 当时接在 4 后面，3 仍大于 -1，必须留下。
Go：Kadane 扫描
func maxSubArray(nums []int) int {current, best := nums[0], nums[0]for i := 1; i < len(nums); i++ {if current+nums[i] > nums[i] {current = current + nums[i]} else {current = nums[i]}if current > best { best = current }}return best}
1用 nums[0] 同时垫上 current 和 best。全负数组时答案会落在最大的那个负数上，不能把 best 初始化成 0。
2if current+nums[i] > nums[i] 就是「带上前面」；否则从 nums[i] 重启。这和 max(nums[i], current+nums[i]) 是同一句话。
3current 只服务「以 i 结尾」这一段，切断之后它会变小。
4best 单独记历史冠军。主例走到 -5 时 current 掉到 1，6 必须已经锁在 best 里。
总结
以当前数结尾：前面和是正的就接着累，是负的就开张；best 另记冠军。主例答案 6。
- 子数组必须连续。跳着捡正数、看见负数就切断，都会在主例上得到小于 6 的错答案。
- current = max(x, current+x) 只问「前面那截是不是累赘」。主例的 -1 当时接在 4 后面，必须留下。
- best 从 nums[0] 起步，只升不降。全负时不会错成 0。