深感人类智慧的伟大啊，，，
第一次看这题简直毫无头绪，
其实状态设出来了，往下推就顺理成章了。
f[i][j][k]表示到第i位，选了j段，第i位有没有选（k）的最大子段和，
然后考虑用人类智慧暴力推倒所有情况的转移方程，
f[i][1][1]:因为要取第i位，又只有一段，所以要么接这上一段来，要么就是新的一段
于是有：f[i][1][1]=max(s[i],f[i-1][1][1]);
f[i][1][0]:因为第i位不取，所以对前面的那一段也就没上面限制了
于是有：f[i][1][0]=max(f[i-1][1][1],f[i-1][1][0]);
f[i][2][0]:因为第i为不取，所以同理，
有 f[i][2][0]=max(f[i-1][2][0],f[i-1][2][1]);
f[i][2][1]:因为要取第i位，所以如果前面就有两段的话，上一位必须取，否则就有3段了，如果前面只有一段，那么就没有限制，
于是：f[i][2][1]=max(f[i-1][2][1],f[i-1][1][1],f[i-1][1][0]);
那么显然这是没有考虑环的情况的，由于段数只有2段，因此我们还是可以暴力枚举情况解决。
显然最大ans只可能由有环参与or没环参与两种情况得来（也没别的情况了）
观察到一个性质，要是对ans的贡献利用到了环，那么有：
第一个必须被选，最后一个也必须被选
这种情况在序列上表现为：
分了3段，其中第一段从第一个开始，最后一段以最后一个结束。
因此我们只需要再DP一次考虑必须有环的情况即可，
推式子的思路与上面类似，下面代码应该写的挺清楚的，可以自己先推一下
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 200100 5 #define getchar() *o++ 6 char READ[2000100],*o=READ; 7 int n,ans; 8 int s[AC],f[AC][4][2]; 9 /*毕竟还是比较妙的，充分体会到了人类智慧的伟大， 10 人工讨论会不会绕会来，人工讨论每一种取法*/ 11 inline int read() 12 { 13 int x=0;char c=getchar();bool z=false; 14 while(c > '9' || c < '0') 15 { 16 if(c == '-') z=true; 17 c=getchar(); 18 } 19 while(c >= '0' && c <= '9') x=x*10+c-'0',c=getchar(); 20 if(!z) return x; 21 else return -x; 22 } 23 24 void pre() 25 { 26 n=read(); 27 for(R i=1;i<=n;i++) s[i]=read(); 28 } 29 30 void work() 31 { 32 memset(f,128,sizeof(f)); 33 for(R i=1;i<=n;i++) 34 { 35 f[i][1][1]=max(s[i],f[i-1][1][1] + s[i]); 36 f[i][1][0]=max(f[i-1][1][1],f[i-1][1][0]); 37 if(i >= 2) 38 { 39 f[i][2][0]=max(f[i-1][2][0],f[i-1][2][1]); 40 f[i][2][1]=max(f[i-1][2][1],max(f[i-1][1][0],f[i-1][1][1])) + s[i]; 41 } 42 } 43 ans=max(f[n][2][0],f[n][2][1]); 44 memset(f,128,sizeof(f));//重新初始化 45 //因为绕回来后在数列上的直接表现就是分成了3段，所以，，， 46 //3段中第一段必须从第一个开始取，最后一段必须一直取到结尾 47 f[1][1][1]=s[1]; 48 for(R i=2;i<=n;i++) 49 { 50 f[i][1][1]=f[i-1][1][1] + s[i];//要是只有一段，还取i的话，一定是取了一整段 51 f[i][1][0]=max(f[i-1][1][0],f[i-1][1][1]); 52 f[i][2][0]=max(f[i-1][2][1],f[i-1][2][0]); 53 f[i][2][1]=max(f[i-1][2][1],max(f[i-1][1][1],f[i-1][1][0])) + s[i];//error。。。取了自己的都要把自己加上啊 54 f[i][3][1]=max(f[i-1][3][1],max(f[i-1][2][1],f[i-1][2][0])) + s[i];//error!!!-1啊啊啊啊 55 //printf("%d = %d %d %d %d %d ",i,f[i][1][0],f[i][1][1],f[i][2][0],f[i][2][1],f[i][3][1]); 56 } 57 ans=max(ans,f[n][3][1]);//因为绕回来了，所以最后一个必须取 58 printf("%d ",ans); 59 } 60 61 int main() 62 { 63 // freopen("in.in","r",stdin); 64 fread(READ,1,2000000,stdin); 65 pre(); 66 work(); 67 // fclose(stdin); 68 return 0; 69 }