题意
需要在o（n）时间内，求最大连续的子序列的和，及其起点和终点。
分析
一种方法是一边读，一边维护最小的前缀和 s[i] ，然后不断更新 ans = max(ans,s[j] - s[i])，以及起始位置。
另一种方法是尺取（算是吧），l 和 r 代表起点和终点，一开始l=0,r=1,如果s[r]-s[l]>=0那就往右扫 r++，不断更新 ans = max(ans,s[r] - s[l])，以及起始位置，如果小于0了，那就舍弃前面这段了，也就是后面必然不用考虑它更划算，l=r，r++。还要注意全是负数的情况，那就只要输出最大的那个负数。
代码
维护min(s[i])
#include <cstdio>
#include <algorithm> using namespace std; int test,n;
int a,k,ans,s[],st,en;
int main()
{
scanf("%d",&test);
for(int t=; t<=test; t++)
{
s[]=;
k=;
ans=-;
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&a);
s[i]=s[i-]+a;
if(s[i]-s[k]>ans){
ans=s[i]-s[k];
en=i;
st=k+;
}
if(s[i]<s[k]){
k=i;
}
}
if(t<test)printf("Case %d:\n%d %d %d\n\n",t,ans,st,en);
else printf("Case %d:\n%d %d %d\n",t,ans,st,en);
}
return ;
}
尺扫
#include <cstdio>
#include <algorithm> using namespace std; int test,n,a,ans,s[],st,en,maxa,maxp;
int main()
{
scanf("%d",&test);
for(int t=; t<=test; t++)
{
maxa=-;
ans=;
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&a);
s[i]=s[i-]+a;
if(a>maxa)
{
maxa=a;
maxp=i;
}
}
if(maxa<)
{
ans=maxa;
st=en=maxp;
}
else
{
int l=;
int r=;
while(r <= n)
{
while(s[r] >= s[l] && r<n)
{
r++;
if(s[r]-s[l]>ans)
{
ans=s[r]-s[l];
st=l+;
en=r;
}
}
l=r;
r++;
}
}
if(t<test)printf("Case %d:\n%d %d %d\n\n",t,ans,st,en);
else printf("Case %d:\n%d %d %d\n",t,ans,st,en);
}
return ;
}