# 题解 P1121 环状最大两段子段和

## 思路

1. ++++++---++++---

2. ++---+++++--++++

f[i] = max(f[i - 1], 0) + a[i];

f[i] = max(f[i - 1], f[i]);

res = max(res, f[i] + g[i + 1]);//注意因为不重叠，所以是g[i + 1]

### 注意

• 若全是非正数，第二次跑会返回$0$（全不选），所以要排除这种情况

• 若只有一个正数，第二次跑会把除它全不选，是错的，要特判

## 代码

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

int n, ans, sum, positive_num;

int a[MAXN], f[MAXN], g[MAXN];

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++;
}
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;
} 

2019-12-01 14:33:35 in 题解