题意
需要在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])
代码语言：javascript复制#include <cstdio>
#include <algorithm>
using namespace std;
int test,n;
int a,k,ans,s[100005],st,en;
int main()
{
scanf("%d",&test);
for(int t=1; t<=test; t )
{
s[0]=0;
k=0;
ans=-1001;
scanf("%d",&n);
for(int i=1; i<=n; i )
{
scanf("%d",&a);
s[i]=s[i-1] a;
if(s[i]-s[k]>ans){
ans=s[i]-s[k];
en=i;
st=k 1;
}
if(s[i]<s[k]){
k=i;
}
}
if(t<test)printf("Case %d:n%d %d %dnn",t,ans,st,en);
else printf("Case %d:n%d %d %dn",t,ans,st,en);
}
return 0;
}尺扫
代码语言：javascript复制#include <cstdio>
#include <algorithm>
using namespace std;
int test,n,a,ans,s[100005],st,en,maxa,maxp;
int main()
{
scanf("%d",&test);
for(int t=1; t<=test; t )
{
maxa=-1001;
ans=0;
scanf("%d",&n);
for(int i=1; i<=n; i )
{
scanf("%d",&a);
s[i]=s[i-1] a;
if(a>maxa)
{
maxa=a;
maxp=i;
}
}
if(maxa<0)
{
ans=maxa;
st=en=maxp;
}
else
{
int l=0;
int r=1;
while(r <= n)
{
while(s[r] >= s[l] && r<n)
{
r ;
if(s[r]-s[l]>ans)
{
ans=s[r]-s[l];
st=l 1;
en=r;
}
}
l=r;
r ;
}
}
if(t<test)printf("Case %d:n%d %d %dnn",t,ans,st,en);
else printf("Case %d:n%d %d %dn",t,ans,st,en);
}
return 0;
}
