C++-HDU1003-Max Sum

时间复杂度O(n)

空间复杂度O(1)

#include <cstdio>
int main() {
    int T;scanf("%d",&T);
    for(int t=1,n,a,l,r,s,L,R,S;t<=T;t++) {
        scanf("%d",&n),l=L=R=1;
        for(r=1;r<=n;r++) {
            scanf("%d",&a),r==1?s=S=a:s+=a;
            if(s>S)S=s,L=l,R=r;
            if(s<0)s=0,l=r+1;
        }
        printf("Case %d:
%d %d %d
",t,S,L,R);
        if(t!=T)printf("
");
    }
    return 0;
}