【题解】
经典的最大子段和问题。如果当前sum大于等于0，就累加上当前的数；当前的sum小于0，就把sum变为0，即之前的那些都不取，因为它们对答案的贡献是负的。扫一遍即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 200010 7 using namespace std; 8 int n; 9 LL sum,ans=-2e9; 10 inline int read(){ 11 int k=0,f=1; char c=getchar(); 12 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 13 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 14 return k*f; 15 } 16 int main(){ 17 n=read(); 18 for(rg int i=1;i<=n;i++){ 19 int x=read(); 20 if(sum<0) sum=x; else sum+=x; 21 ans=max(ans,sum); 22 } 23 printf("%lld ",ans); 24 return 0; 25 }