题目描述

难度分:$1200$

输入$n(1 \leq n \leq 100)$和长为$n$的数组$a$，只包含$0$和$1$。

从$a$中选一个非空连续子数组，把其中的$0$变成$1$，$1$变成$0$。这个操作必须恰好执行一次。

输出操作后$a$中$1$的个数的最大值。

输入样例$1$

5
1 0 0 1 0

输出样例$1$

4

输入样例$2$

4
1 0 0 1

输出样例$2$

4

算法

前缀和+枚举

预处理出$pre$和$suf$两个数组，$pre[i]$表示前缀$[1,i]$中$1$的数量，$suf[i]$表示后缀$[i,n]$中$1$的数量。接下来$O(n^2)$枚举要操作的子数组$[l,r]$即可，维护“$pre[l-1]+suf[r]+1+[l,r]$中$0$的数量”的最大值，这个最大值就是答案。$[l,r]$中$0$的数量可以通过前缀和数组$O(1)$求得。

复杂度分析

时间复杂度

预处理出前缀和与后缀和数组的时间复杂度为$O(n)$。之后枚举非空子数组计算答案，时间复杂度为$O(n^2)$。因此，整个算法的时间复杂度为$O(n^2)$。

空间复杂度

除了输入的$a$数组，空间瓶颈就是两个前缀和数组$pre$和$suf$。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int n, a[N], pre[N], suf[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pre[i] = pre[i - 1] + a[i];
    }
    suf[n + 1] = 0;
    for(int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + a[i];
    }
    int ans = 0;
    for(int l = 1; l <= n; l++) {
        for(int r = l; r <= n; r++) {
            ans = max(ans, pre[l - 1] + r - l + 1 - (pre[r] - pre[l - 1]) + suf[r + 1]);
        }
    }
    printf("%d\n", ans);
    return 0;
}