题目链接：http://www.codeforces.com/problemset/problem/327/A
题意：给定一个01序列，选择一个连续的子段，对其翻转(0变1，1变0)，然后对所有数求和，求最大值。
想法：由于n只有100，所以 O(n3) 的暴力做法可以直接过，即枚举子段的起点和终点。我们不妨考虑下更快速的做法，比如 O(n) 的做法。问题的实质在于求出一个子段，它的值最下，那么一下子问题便化成我们熟悉的最大子段和问题了。我们对于每个0，它反转后的贡献为1，每个1的贡献为-1。然后我们记dp[i]表示以i结尾的最大字段和，则dp[i] = max(d[i - 1], 0) + s[i]。那么答案即为numberOfOne + max{dp[i]}。
代码如下：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <cstdlib> typedef long long ll; const int MAXN = 100 + 10; int s[MAXN], dp[MAXN]; int main(){ int n, ans = 0; scanf("%d", &n); for(int i = 0; i < n; ++i){ int x; scanf("%d", &x); s[i] = x? -1 : 1; if(x){ ++ans; } } dp[0] = s[0]; int mx = dp[0]; for(int i = 1; i < n; ++i){ dp[i] = std::max(dp[i - 1], 0) + s[i]; mx = std::max(dp[i], mx); } printf("%d\n", ans + mx); return 0; }