文章

25

粉丝

0

获赞

210

访问

5.1k

头像
字符串区间翻转 题解:
P1642 杭州电子科技大学/南京大学机试题
发布于2026年3月15日 11:30
阅读数 121

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

const int N = 1e7 + 5;
int dp[N];
int a[N];

int main(){
    int n;
    string s;
    while(cin >> n){
        cin >> s;
        int total = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1'){
                a[i] = -1;
                total ++;
            }else{
                a[i] = 1;
            }
        }

        dp[0] = a[0];
        int ans = (-1) * 1e7;
        for(int i = 1; i < n; i++){
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + a[i];
                ans = max(ans, dp[i]);
            }else{
                dp[i] = a[i];
                ans = max(ans, dp[i]);
            }
        }
        
        if(ans < 0) ans  = 0;
        printf("%d\n",ans + total);
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发