hello

Menu

【学习算导】最大子串

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

做法如下:

暴力就不说了

分治这个做法在算导里讲得十分详细,取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]以后的数字都是没有贡献的:

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

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

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

— 于 共写了750个字
— 文内使用到的标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注