求环状最大和子序列 方法是 先求出 不循环的情况下的 最大和子序列 , 和最小和子序列 , 然后 所有数字的和-最小和子序列 和 最大和自序列里面找一个 最大值 就是 最终的最大值
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #include<iostream>
5 #include<algorithm>
6 #include<queue>
7 #include<vector>
8 #include<set>
9 #include<stack>
10 #include<string>
11 #include<sstream>
12 #include<map>
13 #include<cctype>
14 #include<limits.h>
15 using namespace std;
16 long long n,t,s,m1,m2,s1,s2;
17 int main()
18 {
19 while(scanf("%lld",&n)!=EOF)
20 {
21 scanf("%lld",&t);
22 s=m1=m2=s1=s2=t;
23 for(int i=1;i<n;i++)
24 {
25 scanf("%lld",&t);
26 s+=t;
27 if(s1>0)
28 s1=s1+t;
29 else
30 s1=t;
31 m1=max(m1,s1);
32 if(s2<0)
33 s2+=t;
34 else
35 s2=t;
36 m2=min(s2,m2);
37 }
38 printf("%lld
",max(m1,s-m2));
39 }
40 return 0;
41 }