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

思路

观察题目，发现不管怎么选，都只有两种情况：

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（全不选），所以要排除这种情况

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

自己想想为什么，对以后的变形会有好处

代码

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

日拱一卒，功不唐捐