我来一发很实用的题解；
本人想出了O(n)的做法，是一种DP；
先说大体思路:
答案分两种情况，一种是选择的两段均不跨越n到1(也就是环)，另一种是选择的两段跨过了环;
如果均不跨越环，那么也就是意味着这是一道模板题；
设maxl[i]表示从1~i的最大字串和，maxr[i]表示i~n的最大字段和；
很明显的:答案就是max(maxl[i]+maxr[i+1])
```cpp
maxl[i]=max(a[i],maxl[i-1]+a[i]);//表示这一位是不是一段区间的开头；
maxl[i]=max(maxl[i-1],maxl[i]);
maxr[i]=max(a[i],maxr[i+1]+a[i]);
maxr[i]=max(maxr[i],maxr[i+1]);
```
所以目前你的期望分数就是50了；
然后处理环：
我们换种思维，就好比并查集维护联通时可以运用逆向思维一样，把拆边改为加边，你求1~n带环的最大值就等价于求(1~n的区间和)减去(1~n的两段区间最小值)
求最小值的方法和求最大值的方法是一样的，稍加更改就可以了；
然后期望分数100
然后就A了吗？
嗯~？怎么才打了80分？
你跑一遍程序，试试这组数据:
3
-2 -4 -5
你的多少？0？正解是-6啊！
这是因为题中要求是两段非空的字串，所以当整个串都是负数时应该特判，选择最大的两个值加起来就是答案了；
#include <bits/stdc++.h> #define int long long using namespace std; long long a[200010]; long long maxl[200010],minl[200010],maxr[200010],minr[200010]; signed main() { int n; cin>>n; long long sum=0; long long maxn=-999999999999; for(register int i=1;i<=n;i++){ cin>>a[i]; maxn=max(maxn,a[i]); sum+=a[i]; } for(register int i=1;i<=n;i++){ maxl[i]=maxr[i]=-999999999999; minl[i]=minr[i]=999999999999; } maxl[1]=a[1]; minl[1]=a[1]; maxr[n]=a[n]; minr[n]=a[n]; for(register int i=2;i<=n;i++){ maxl[i]=max(a[i],maxl[i-1]+a[i]); minl[i]=min(a[i],minl[i-1]+a[i]); } for(register int i=2;i<=n;i++){ maxl[i]=max(maxl[i-1],maxl[i]); minl[i]=min(minl[i-1],minl[i]); } for(register int i=n-1;i>=1;i--){ maxr[i]=max(a[i],maxr[i+1]+a[i]); minr[i]=min(a[i],minr[i+1]+a[i]); } for(register int i=n-1;i>=1;i--){ maxr[i]=max(maxr[i],maxr[i+1]); minr[i]=min(minr[i],minr[i+1]); } long long anspart1=-999999999999,anspart2=999999999999; for(register int i=1;i<=n;i++){ anspart1=max(anspart1,maxl[i]+maxr[i+1]); anspart2=min(anspart2,minl[i]+minr[i+1]); } long long ans=max(anspart1,sum-anspart2); sort(a+1,a+1+n); if(sum==anspart2){ ans=a[n]+a[n-1]; } cout<<ans; } /* 6 3 2 -1 1 -1 5 8 -5 -8 -23 -5 -6 -7 -12 -6 -7 */
原文：https://www.cnblogs.com/kamimxr/p/11438701.html