终于AC了，刚开始写这题很容易写成O(n*n)的算法，实际上O(n)就可以解决。
solve1:最大子段和没有收尾相连，正常数组的字段和最大就可以
solve2:收尾相连，此时求正常数组中间负数绝对值和最大的那一段，然后用总和减去.
讲解：这里写链接内容
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 600010
typedef long long ll;
using namespace std;
ll a[maxn],sum[maxn],dp1[maxn],dp2[maxn];
ll n,t=0;
int main(){std::ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t+=a[i];dp1[i]=dp1[i-1]+a[i];dp2[i]=dp2[i-1]+a[i];}ll ans=-inf,tmp=inf;for(int i=1;i<=n;i++){//solve1if(dp1[i-1]>0){dp1[i]=dp1[i-1]+a[i];}else{dp1[i]=a[i];}//solve2if(dp2[i-1]<0){dp2[i]=dp2[i-1]+a[i];}else{dp2[i]=a[i];}ans=max(ans,dp1[i]);tmp=min(tmp,dp2[i]);}if(tmp<0) tmp=t-tmp;// for(int i=0;i<=n;i++){
// cout<<dp1[i]<<" ";
// }
// cout<<endl;//cout<<tmp<<" "<<ans<<endl;cout<<max(tmp,ans)<<endl;return 0;
}
O(N*N),肯定是TLE。后面调。
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 600010
typedef long long ll;
using namespace std;
ll a[maxn],sum[maxn];
ll n,t=0;
int main(){std::ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t+=a[i];sum[i]=sum[i-1]+a[i];}//solve1:最大子段和没有收尾相连，正常数组的字段和最大就可以//solve2:收尾相连，此时求正常数组中间负数绝对值和最大的那一段，然后用总和减去ll ans=-inf,tmp=inf;for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){ans=max(sum[i]-sum[j],ans);tmp=min(sum[i]-sum[j],tmp);}}if(tmp<0) tmp=t-tmp;else tmp=t+tmp;// cout<<t<<" "<<tmp<<" "<<ans<<endl;cout<<max(tmp,ans)<<endl;return 0;
}