最大子串

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

做法如下：

暴力
分治
瞎搞线性遍历

暴力就不说了

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

子串在mid左边
子串在mid右边
子串横跨了mid

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

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

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

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

实现起来也脉络清晰明了

#include <cstdio>

#include <iostream>

using namespace std;

const int _maxn=100010,inf=2100000000;

struct e{

int l,r,sum;

//重定义 >=

bool operator >= (e y){

return sum>=y.sum;

}

}ans;

int a[_maxn];

//对第3种情况的遍历

e calc(int l,int mid,int r){

e b;

int sum,min_left,max_right;

int l_sum,r_sum;

//从中间往两边遍历

l_sum=-inf;

sum=0;

for(int i=mid;i>=l;i--){

sum+=a[i];

if(sum>l_sum){

l_sum=sum;

min_left=i;

}

r_sum=-inf;

sum=0;

for(int i=mid+1;i<=r;i++){

sum+=a[i];

if(sum>r_sum){

r_sum=sum;

max_right=i;

}

b.l=min_left;

b.r=max_right;

b.sum=l_sum+r_sum;

return b;

}

e find(int l,int r){

if(l==r){

e b;

b.l=l;

b.r=r;

b.sum=a[l];

return b;

}

else{

e bl,br,bc;

int mid=(l+r)>>1;

bl=find(l,mid); //第一种情况

br=find(mid+1,r); //第二种情况

bc=calc(l,mid,r); //第三种情况

//三种情况取最大值

if(bl>=bc && bl>=br)

return bl;

else if(br>=bl && br>=bc)

return br;

else

return bc;

}

int main(){

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

ans=find(1,n);

printf("%d->%d=%d\n",ans.l,ans.r,ans.sum);

return 0;

}

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

a[j+1]>0,则sum[i,j+1]一定比sum[i,j]大，此时可以更新最优解
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)

//此代码不太适用于有零的情况，仅供参考

#include <iostream>

#include <cstdio>

using namespace std;

int main(){

int x,n,sum=0,left=1,ansleft,ansright,ans=-2100000000;

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d",&x);

sum+=x;

if(sum<0){

sum=0;

left=i+1;

continue;

}

if(sum>ans){

ansleft=left;

ansright=i;

ans=sum;

}

printf("%d->%d=%d\n",ansleft,ansright,ans);

return 0;

}

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

-- 热度:1,965 ℃
-- 于 2018年09月23日，共写了750个字；
-- 文内使用到的标签：

2条回应：“最大子串”