解题思路:
注意事项:
参考代码:#include
#include
#include
#include
#include
#include
usingnamespacestd;
constintmaxn=100001;
inta[maxn];
intmaxsum(int*A,intx,inty)//返回左闭右开区间[x,y)中的最大连续和
{
intv,L,R,maxs;
if(y-x==1)returnA[x];
intm=x+(y-x)/2;//划分
maxs=max(maxsum(A,x,m),maxsum(A,m,y));
v=0;
L=A[m-1];
for(inti=m-1;i>=x;--i)//合并
{
L=max(L,v+=A[i]);
}
v=0;
R=A[m];
for(inti=m;i
{
R=max(R,v+=A[i]);
}
returnmax(maxs,L+R);
}
intmain()
{
intT;
scanf("%d",&T);
for(inti=0;i
{
scanf("%d",&a[i]);
}
printf("%d\n",maxsum(a,0,T));
return0;
}