Pre

专业挖坑，这个坑是去年挖的，现在已经发霉了。

Solution

先做一次最大子段，再做一次全部取负的最大子段，就可以了。

注意特判如果不成立的情况，也就是取负之后可能选的只剩下一个，这时是只有一个正数的情况。

或许还有全部负数的情况，题解没说要特判，我还是一起判了。

Code

#include <cstdio> #include <cstring> #include <limits.h> using namespace std; inline int max (int u, int v) { return u > v ? u : v; } const int N = 200000 + 5; int lans[N], rans[N], f[N]; inline int work (int*a, int n) { lans[0] = rans[n + 1] = INT_MIN; memset (f, 128, sizeof f); for (int i = 1; i <= n; ++i) { f[i] = max (a[i], f[i - 1] + a[i]); lans[i] = max (f[i], lans[i - 1]); } memset (f, 128, sizeof f); for (int i = n; i >= 1; --i) { f[i] = max (a[i], f[i + 1] + a[i]); rans[i] = max (f[i], rans[i + 1]); } int res = INT_MIN; for (int i = 2; i <= n; ++i) { res = max (res, lans[i - 1] + rans[i]); } return res; } int a[N], n, sum, ans = INT_MIN, t; int main () { #ifdef chitongz freopen ("x.in", "r", stdin); #endif scanf ("%d", &n); for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]), sum += a[i], t += a[i] > 0; ans = max (ans, work (a, n)); for (int i = 1; i <= n; ++i) a[i] *= -1; if (t > 1) ans = max (ans, sum + work (a, n)); printf ("%d\n", ans); return 0; }

Conclusion

这个是去年 \(10\) 月看上的题目，现在才做。。。

注意这种题目的坑。

转载于:https://www.cnblogs.com/ChiTongZ/p/11375210.html

相关资源：JAVA上百实例源码以及开源项目