P76039 翻转连续区间 — 题解

专题： 动态规划
适用题目： 新生 OJ 本地题包中的 P76039，不要直接用于外站同名题。

解题思路

翻转一段区间，相当于每个 0 带来 +1、每个 1 带来 -1；求最大非空子段和并加上原本 1 的个数。

复杂度

时间 $O(n)$，额外空间 $O(1)$。

易错点

必须翻转非空区间；全是 1 时结果要减少 1。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n;scanf("%d",&n);
    long long ones=0,cur=-1000000000,best=-1000000000;
    for(int i=0;i<n;i++){
        int x;scanf("%d",&x);ones+=x;
        long long gain=x?-1:1;
        cur=(cur+gain>gain)?cur+gain:gain;
        if(cur>best)best=cur;
    }
    printf("%lld\n",ones+best);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    ll ones=0,cur=LLONG_MIN/4,best=LLONG_MIN/4;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        ones+=x;
        ll v=x?-1:1;
        cur=max(v,cur+v);
        best=max(best,cur);
    }
    cout<<ones+best<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。