题解 P1121 环状最大两段子段和
ctq1999
2019-12-01 14:33:35
## 思路
观察题目，发现不管怎么选，都只有两种情况：
```
1. ++++++---++++---
2. ++---+++++--++++
```
即要么是选两段的（对应$1.$），要么是有两段不选的（对应$2.$）
这样想就会把环拆成一条链
那么对于$1.$，我们可以从头尾两端去扫描数组，设$f[i]$为$1-i$和最大的连续的一段：
```
f[i] = max(f[i - 1], 0) + a[i];
```
这样保证了扫描一遍后的$f[i]$必定是在以$i$结尾一个连续的一段中
但并不是最优的那一段，因为在$1-i$中最优的一段可能不以$i$结尾
所以再扫描一遍数组：
```
f[i] = max(f[i - 1], f[i]);
```
便得到了$1-i$中和最大的连续的一段
因为是两段，所以设$g[i]$为$i-n$中和最大的连续的一段，再扫两遍，比较一下：
```
res = max(res, f[i] + g[i + 1]);//注意因为不重叠，所以是g[i + 1]
```
这是第一种情况的做法
第二种求最优的三段的和，那么也就是总和减去不要的两段
那么把上面的$max$改成$min$就可以求出不要的两段的和了
更简单的方法：把$a$数组正负翻转，直接跑，最后是$sum+ask()$（因为符号变了）
### 注意
- 若全是**非正数**，第二次跑会返回$0$（全不选），所以要排除这种情况
- 若只有**一个正数**，第二次跑会把除它全不选，是错的，要特判
*自己想想为什么，对以后的变形会有好处*
## 代码
```cpp
#include <bits/stdc++.h>
#define MAXN 200010
using namespace std;
int n, ans, sum, positive_num;
int a[MAXN], f[MAXN], g[MAXN];
int ask() {
int res = -MAXN;
for (int i = 1; i <= n; i++) f[i] = max(f[i - 1], 0) + a[i];
for (int i = n; i >= 1; i--) g[i] = max(g[i + 1], 0) + a[i];
for (int i = 1; i <= n; i++) f[i] = max(f[i - 1], f[i]);
for (int i = n; i >= 1; i--) g[i] = max(g[i + 1], g[i]);
for (int i = 1; i < n; i++) res = max(res, f[i] + g[i + 1]);
return res;
}
int main() {
scanf("%d", &n);
memset(f, ~0x7f, sizeof(f));
memset(g, ~0x7f, sizeof(g));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
if (a[i] > 0) positive_num++;
}
ans = ask();
if (positive_num == 1) {
cout << ans << endl;
return 0;
}
for (int i = 1; i <= n; i++) a[i] *= -1;
ans = max(ans, sum + ask() ? sum + ask() : -MAXN);
cout << ans << endl;
return 0;
}
```
> 日拱一卒，功不唐捐