首页 > 代码库 > 最大连续子序列和

最大连续子序列和

对于给定的数组 numnum,一个长度为 ss 的连续子序列是指由 num_i,num_{i+1},num_{i+2}\ldots,num_{i+s-1}num?i??,num?i+1??,num?i+2??…,num?i+s−1?? 组成的序列。数组中的元素有可能为正数、负数或 00。你需要从数组中找出元素总和最大的一个连续子序列。

比如,对于数组 1,-3,2,6,-5,81,3,2,6,5,8,其最大连续子序列之和是 2+6-5+8=112+65+8=11。

对于一段区间内的最大连续子序列和,我们能不能借助分治思想,将这个大问题拆分成两个子问题,然后将两个子问题的解合并为大问题的解呢?

解法

我们记录一段子区间 [x,y][x,y] 的三个结果:从最左端向右的最大连续子序列 [x,y]_{lmax}[x,y]?lmax??、从最右端向左的最大连续子序列 [x,y]_{rmax}[x,y]?rmax??、区间内的最大连续子序列 [x,y]_{max}[x,y]?max??(没有是否靠着某个端点的限制)。

对于区间 [a,b][a,b],我们可以先递归地求解两个子区间 [a,mid],[mid+1,b][a,mid],[mid+1,b] 的三个值 lmax,rmax,maxlmax,rmax,max。之后,对两个子区间进行合并:

  • 对 [a,b][a,b] 区间从左向右循环扫描,计算 [a,b]_{lmax}[a,b]?lmax??;
  • 对 [a,b][a,b] 区间从右向左循环扫描,计算 [a,b]_{rmax}[a,b]?rmax??;
  • 将 [a,b]_{lmax}[a,b]?lmax??、[a,b] _{rmax}[a,b]?rmax??、[a,mid] _{rmax}+[mid+1,b] _{lmax}[a,mid]?rmax??+[mid+1,b]?lmax??、[a,mid] _{max}[a,mid]?max??、[mid+1,b] _{max}[mid+1,b]?max?? 这五个数的最大值作为 [a,b] _{max}[a,b]?max?? 的结果,结束当前区间的计算。

这个算法和归并排序非常像,时间复杂度也和归并排序一致,是稳定的 \mathcal{O}(nlogn)O(nlogn)。

最大连续子序列和