自动搬运

查看原文

来自洛谷，原作者为

	hwx12233 这个人废了，什么都没留下

搬运于2025-08-24 22:12:57，当前版本为作者最后更新于2019-11-13 20:12:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

嗯，这道题有点水。。

就是求一个最大子段和

解法

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

这里介绍一种新的

又显然 我们可以：

遇到$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;
}

谢谢观看！