题目描述

难度分:$883$

给你一个长度为$N$（$N \in [1,3 \times 10^5]$）的整数序列，由$0$和$1$组成：$A=(A_1,A_2,⋯,A_N)$

下面的操作您只需做一次。

• 选择$A$的一个连续子序列，翻转其中的元素：将$0$转换为$1$，反之亦然。在这里，你可以选择一个空的子序列，在这种情况下，$A$中的元素不会改变。

您的得分将是$A$中$1$的个数。您的分数可以取多少个值？

输入样例$1$

4
0 1 1 0

输出样例$1$

4

输入样例$2$

5
0 0 0 0 0

输出样例$2$

6

输入样例$3$

6
0 1 0 1 0 1

输出样例$3$

3

算法

动态规划

这个题本质上就是找在所有子数组中，$1$的个数$count[1]$减去$0$的个数$count[0]$（或$0$的个数减去$1$的个数）有多少种不同的值，因为只有$count[1]-count[0]$不一样才会导致子数组01反转后发生和的变化。因此，将$0$当成$-1$，求一下最大子段和$mx$与最小子段和$mn$就行，区间$[mn,mx]$中的取值应该都是可以达成的。

这个动态规划非常经典，这里不做赘述，主要问题在于为什么$[mn,mx]$区间内的值都可以达成。因为子数组往外扩张一格要么是增加一个$1$，要么是增加一个$0$，因此$count[1]-count[0]$的变化应该是连续的，$[mn,mx]$都可以取到。

复杂度分析

时间复杂度

遍历一遍原数组$a$求最大子段和以及最小子段和，都是线性的复杂度，时间复杂度为$O(n)$。

空间复杂度

开辟了两个DP数组进行动态规划，额外空间复杂度为$O(n)$（也可以滚动优化到$O(1)$）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 300010;
int n, a[N], dp_max[N], dp_min[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] == 0) --a[i];
    }
    int lb = 0, ub = 0;       // 初始化为一个数都不选
    for(int i = 1; i <= n; i++) {
        dp_max[i] = max(dp_max[i - 1] + a[i], a[i]);
        dp_min[i] = min(dp_min[i - 1] + a[i], a[i]);
        ub = max(ub, dp_max[i]);
        lb = min(lb, dp_min[i]);
    }
    printf("%d\n", ub - lb + 1);
    return 0;
}