对于一个01字符串的最大字段和(0变成1,1变成-1)90分求助
  • 板块学术版
  • 楼主qip101
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/11/11 12:42
  • 上次更新2023/10/27 03:26:16
查看原帖
对于一个01字符串的最大字段和(0变成1,1变成-1)90分求助
333800
qip101楼主2022/11/11 12:42
#include <bits/stdc++.h>
#define MAXN 5005000
using namespace std;
long long len,a[MAXN],f[MAXN],ans;
string s; 
int main()
{
	cin >> s;
	len=s.length();
	for(int i=0;i<len;i++)
	{
		if(s[i]=='1')
			a[i]=-1;
		if(s[i]=='0')
			a[i]=1;
	}
	//最大子段和
	for(int i=0;i<len;i++)
		f[i]=max(f[i-1]+a[i],a[i]);
	for(int i=0;i<len;i++) 
		ans=max(ans,f[i]);
	cout << ans << endl;
	return 0;
}

2022/11/11 12:42
加载中...