维护前缀和的最小值,然后枚举区间右端点
因为对于端点r,只需求S[r]-S[l-1]的最大值
故维护S(i) (i<r)的最小值即可得解
算法复杂度O(n)

#include<iostream>
#include<algorithm>
using namespace std;
int a[200001],s[200001],n;
int main(){
    int i;
    int mins=0,ans=0;
    s[0]=0;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(i=1;i<=n;i++){
        ans=max(ans,s[i]-mins);//记录答案 
        mins=min(mins,s[i]);//维护左侧前缀和序列的最小值 
    }
    cout<<ans;
}

30分/60分解法
30分直接求所有正数的和
60分,枚举区间,维护前缀和,剪枝排除区间端点为负数的情况即可

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[200001],s[200001],n;
int main(){
    register int i,j,ans=0;
    ios::sync_with_stdio(false);
    cin>>n;
    s[0]=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    bool flag=true;
    for(i=1;i<n;i++){//检测是否为单调递增
        if(a[i+1]<a[i]){
            flag=false;
            break;
        }
    }
    if(flag){//30分解法 
        for(i=1;i<=n;i++) if(a[i]>0) ans+=a[i];
    }
    else{//60分解法 
        for(i=1;i<=n;i++){
            if(a[i]<0) continue; //区间端点不能为负数 
            for(j=i;j<=n;j++){
                ans=max(ans,s[j]-s[i-1]);
            }
        }
    }
    cout<<ans;
}