B – Count 1's

题目描述：

给你一个01序列，一个区间[l, r]的价值是区间中1的数量，问所有自区间的不同的价值的数量

思路：

假设[1, n]中有num个1, [l, r]中有a个1,b个0，则区间的1的数量是num + b - a, 不同的区间的num是不变的，变化的是b-a,也就是0和1的数量差，所以我们可以把0的位置变为-1，1的位置还是1，这样的区间和就是数量差了，现在就是问一个只有-1和1的数组的区间和有多少种不同的数

因为数字都是1，-1，所以我们可以最大区间子段和，最小区间子段和，二者的差值就是答案

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        if(!tr[i])tr[i] = -1;
    }
    int maxn = 0;
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        sum += tr[i];
        if(sum < 0)sum = 0;
        else maxn = max(maxn, sum);
    }
    for(int i = 1; i <= n; ++i)tr[i] = -tr[i];
    int maxnn = 0;
    sum = 0;
    for(int i = 1; i <= n; ++i){
        sum += tr[i];
        if(sum < 0)sum = 0;
        else maxnn = max(maxnn, sum);
    }
    cout << maxn + maxnn + 1 << endl;
}


int main(){
    io;
    work();
    return 0;
}