CSU

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1529

题解：

一个加强版的最大连续和子序列，序列可以从末尾元素转到首元素。

分两种情况：

1.最大连续和不需要尾接首，直接dp出以a[i]为结尾的最大连续和ma[i]。

2.最大连续和需要尾接首，先dp出以a[i]为结尾的最小连续和mi[i]，然后再用总和sum减去mi[i],得到的即为减去中间部分的尾接首序列和（逆向思维）。最后再用max()取最大值。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define ms(a, b)  memset((a), (b), sizeof(a))
16 #define eps 0.0000001
17 #define LNF (1<<60)
18 typedef long long LL;
19 const int inf = 0x3f3f3f3f;
20 const int maxn = 2000000+10;
21 const int mod = 1e9+7;
22 
23 LL a[maxn], ma[maxn], mi[maxn];
24 
25 int main()
26 {
27     int T, n;
28     scanf("%d", &T);
29     while(T--)
30     {
31         LL sum = 0;
32         scanf("%d",&n);
33         for(int i = 1; i<=n; i++)
34             scanf("%lld",&a[i]), sum += a[i];
35 
36         for(int i = 1; i<=n; i++)//最大连续和
37             ma[i] = max(ma[i-1], 0LL) + a[i];
38 
39         for(int i = 1; i<=n; i++)//最小连续和
40             mi[i] = min(mi[i-1], 0LL) + a[i];
41 
42         LL ans = ma[1];
43         for(int i = 1; i<=n; i++)//寻找最大值
44         {
45             ans = max(ans, ma[i]);
46             ans = max(ans, sum-mi[i]);
47         }
48 
49         printf("%lld
",ans);
50     }
51     return 0;
52 }

View Code