文章
1
粉丝
0
获赞
5
访问
74
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1e7 + 10;
int dp[N];
int main()
{
int n;
string str;
while(cin >> n >> str)
{
// 统计1的数量
int cnt = 0;
for (int i = 0; i < n; i ++)
{
if (str[i] == '1') cnt ++;
}
vector<int> w;
for (int i = 0; i < n; i ++)
{
if (str[i] == '1') w.push_back(-1);
else w.push_back(1);
}
// 计算以i为结尾区间反转的最大收益, 可能为负
dp[0] = w[0];
int res = 0; // 最坏情况一个都不不反转,收益为0
for (int i = 1; i < n; i ++)
{
dp[i] = max (dp[i-1] + w[i], w[i]);
res = max (res, dp[i]);
}
cout << cnt + res << endl;
memset(dp, 0, sizeof(int)*n);
}
}
登录后发布评论
暂无评论,来抢沙发