正经题解｜变换数字

题目大意

给你 $n$ 个数，只包含 $0$ 与 $1$。
可以操作一次，选择一个区间 一定要选择。

将区间内的 $1$ 变为 $0$，$0$ 变为 $1$。

题意分析

问操作一次后，最多剩余多少个 $1$。

解题思路

我们可以记一下原序列每个区间 $1$ 的数量，这个时候你应该要能想到前缀和。
用前缀和记录 1 ~ n 之间 $1$ 的数量，用数组 $sum$ 记录。

既然我能够知道每个区间 $1$ 的数量，就能推算出 $0$ 的数量。

比如我现在选择一个区间 $[L,R]$，那么这个区间 $0$ 的数量就是，$(R - L + 1) - (sum[R] - sum[L-1])$。

最后我们可以枚举所有的区间情况。

时间复杂度分析

求前缀和 $O(n)$

枚举区间 $O(n ^ 2)$

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 3000;
int x;
int sum[N];
int main() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=1;i<=n;i++) {
        cin >> x;
        sum[i] = sum[i-1] + x;
    }
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            int cnt = sum[i-1];
            cnt += (j - i + 1) - (sum[j] - sum[i-1]);
            cnt += sum[n] - sum[j];
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
    return 0;
}