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

不难发现，我们能选择的集合只有下面两种情况： $1.\ \ \ (000)111(000)111(000)$ $2.\ \ \ 111(000)111(000)111$ 0旁边的括号表示：中间的0可以省略也符合题意 我们两种情况分开考虑 对于第一种情况，我们枚举一个断点，对两端分别做最大子段和。 举个例子，我们可以分别对$[1, 5]\ \ [6, 10]$分别做最大子段和，答案即是两端最大子段和相加的值 每一次左端点仅仅向右移一位，右端点仅仅向左移动一位，所以我们每次没有必要重新算最大子段和，只需记:$left[i]$表示$[1, i]$的最大子段和，$right[i]$表示$[i, n]$的最大子段和即可。 对于第二种情况，我们可以用总和-两段最小子段和，两端最小子段和的求法同上 但是有一个更巧妙的方法：最小子段和=将原数组取反后的最大子段和。证明的话感性理解即可。 于是我们只需要将原数组取反，再做一遍第一种情况即可 ```` ```` 还有本题需要注意一个地方：如果我没有正数，或者只有一个正数，对于第二种情况，我们取反后会变成只有一个负数或者没有，所以我们的最大字段和可能取到$[1, i - 1]\ \ [i + 1, n]$，由于我们第二种情况的意义是不能取这些数，所以对于上述情况我们实际上是指选了1个数的，很明显这不符合题意，于是我们需要加特判 ### $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define inf 123456789 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define maxn 200005 int n, m, a[maxn], dp[maxn], lef[maxn], rig[maxn], ans1, ans2, sum, m1, m2, tot; il void doit(int l, int r) { dp[l - 1] = dp[r + 1] = lef[l - 1] = rig[r + 1] = -inf; rep(i, l, r) dp[i] = max(dp[i - 1], 0) + a[i], lef[i] = max(lef[i - 1], dp[i]); drep(i, l, r) dp[i] = max(dp[i + 1], 0) + a[i], rig[i] = max(rig[i + 1], dp[i]); } il void solve(int x) { sum += x, tot += (x > 0); if(x >= m1) m2 = m1, m1 = x; else if(x >= m2) m2 = x; } int main() { n = read(), ans1 = ans2 = m1 = m2 = -inf; rep(i, 1, n) a[i] = read(), solve(a[i]); if(tot < 2) return printf("%d", m1 + m2), 0; doit(1, n); rep(i, 2, n - 1) ans1 = max(ans1, lef[i - 1] + rig[i + 1]); rep(i, 1, n) a[i] = -a[i]; doit(1, n); rep(i, 2, n - 1) ans2 = max(ans2, lef[i - 1] + rig[i + 1]); printf("%d", max(ans1, sum + max(0, ans2))); return 0; } ```