题解 P5650 【基础字符串练习题】

· · 题解

嗯，这道题有点水。。

就是求一个最大子段和

解法

显然我们可以求前缀和，然后求解，但是有点慢？吧

这里介绍一种新的

又显然 我们可以：

遇到0当前最优解就+1,并与全局最优解取max

遇到1当前最优解-1，并与0取min（因为如果小于0，那么不如不选这前面的所有）

设一个ans1记录部分最优解，ans2记录到全局的最优解（ans2记得初始值为-1，防止所有都是1的情况）

最后奉上代码，码风炸裂，大佬勿喷。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int max(int x,int y){return x>y?x:y;}
#define int ll
int n;char s[100501];
signed main()
{
    cin>>s;int ans1=0,ans2=-1;
    n=strlen(s);
    for(int i=0;i<n;i++){
        int tmp=s[i]-'0';
        if(tmp==0){
            ans1++;
            ans2=max(ans1,ans2);
        }
        else 
            ans1=max(0,ans1-1);
    }
    cout<<ans2;
}

谢谢观看！