【学习算导】最大子串

在一个数字序列中，找到一个子串序列，使得这个子串各个数字的和最大

做法如下：

• 暴力
• 分治
• 瞎搞线性遍历

暴力就不说了

分治这个做法在算导里讲得十分详细，取mid为序列的中间位置，则这个子串在序列中有三种情况：

1. 子串在mid左边
2. 子串在mid右边
3. 子串横跨了mid

对于1、2两种情况，可以直接递归继续二分讨论这三种情况，直到二分到只剩下一个值，此时直接返回该值的左右位置下标（其实是同一个下标），和它的值。

对于第3种情况，也不麻烦，只需要对当前区间来一遍遍历即可讨论出这种情况。

最后对三种情况取一个最大值回溯就行了。

由于这个分治策略属于一种二分，所以该分治树有logN层高，每层都只有第三种情况遍历了N个值，故时间复杂度为O(nlogn)

实现起来也脉络清晰明了

假如当前有一子串是sum[i,j]=a[i]->a[j]，那么对于a[j+1]就有两种情况（不考虑a[j+1]=0）：

1. a[j+1]>0,则sum[i,j+1]一定比sum[i,j]大，此时可以更新最优解
2. a[j+1]<0,则sum[i,j+1]一定比sum[i,j]小，直接接纳a[j+1]

但是万一a[j+1]一直过了很久才出现正数怎么办？也许出现正数以后就不再有负数那又要怎么更新？

于是就可以规定，当sum[i,j]<0时，就从零再来

因为当sum[i,j]<0,那么从a[j]以前的和对a[j+1]以后的数字都是没有贡献的:

• 显而易见，当i<=m<=j时，总有sum[m,j]<0

所以此时，我们就应该从零再来累计了

这样，实现起来就轻松多了，没有任何累赘，每个数字只需要判断一次，时间复杂度是O(n)

代码未经过题目的洗礼，错了不怪我 （ 逃