题意

解析

纯暴力枚举，先计算总1数。第一维枚举左端点，第二维枚举右端点，第三维从左端点跑到右端点计算当前区间如果原来是1则减1，原来是0则加1。
前缀和优化。一个翻转是1-a[x]，区间反转就是这个区间长度-区间和，然后加上剩余的区间和即可。
区间DP。f[i][j]代表的是将i~j这段反转后的最多的1数。
f[i][j] = max(f[i+1][j] + (1 - a[i]),f[i][j-1] + (1 - a[j])); 那此时最后的答案并不是f[i][j]，而是过程中所有的区间的方案里选个最大的。
思维，最大子段和。要将某个区间反转，那也就是说这个区间里原来0的数量要尽可能多，1的数量尽可能少。可以这样假设，1的贡献是-1，0的贡献是1，那原样例10010，就变成了-1 1 1 -1 1。也就是求这个序列的最大子段和，也就求出了能够提供最大新贡献的区间。最后再加上原有1的数量。这样的写法有一个缺陷，就是数列里可能有全1，答案不应该输出序列长度，因为题目要求必须反转，那么就只反转一个好了，需要加个特判。

代码

暴力 O(N^3)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 10,M = 1e6 + 10;
int n;
int a[N],sum,res;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int s = sum;
            for(int k=i;k<=j;k++){
                if(a[k]) s--;
                else s++;
            }
            res = max(res,s);
        }
    }

    cout << res;
    return 0;
}

暴力前缀优化 O(N^2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 10,M = 1e6 + 10;
int n;
int a[N],s[N],res,f[N][N];
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            res = max(res,(j-i+1) - (s[j] - s[i-1]) + s[i-1] + s[n] - s[j]);
        }
    }
    cout << res;
    return 0;
}

区间DP O(N^2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 10,M = 1e6 + 10;
int n;
int a[N],s[N],res,f[N][N];
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }

    for(int i=1;i<=n;i++){
        f[i][i] = 1 - a[i];
        res = max(res,f[i][i] + s[i-1] + s[n] - s[i]);
    }
    
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j = i + len - 1;
            f[i][j] = max(f[i+1][j] + (1 - a[i]),f[i][j-1] + (1 - a[j]));
            res = max(res,f[i][j] + s[i-1] + s[n] - s[j]);
        }
    }
    cout << res;
    return 0;
}

思维最大子段和 O(N)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 10,M = 1e6 + 10;
int n;
int a,sum,res,ans,ok;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a;
        if(a){
            res++;
            if(sum > 0) sum--;
        }else{
            ok = 1;
            sum++;
        }
        ans = max(ans,sum);
    }
    if(!ok) cout << n - 1;
    else cout << res + ans;
    return 0;
}