ACM:疯狂的01串

我们定义一个串是平衡字符串当且仅当这个字符串包含相同个数的0和1，比如：0011、110010是平衡字符串，而1101、0000不是平衡字符串。
现在给你一个串，你需要告诉我这个串的最长平衡子串的长度和最长平衡子序列的长度分别是多少。
输入
第一行是一个正整数 n 代表字符串的长度。 (1 <= n <= 100000)
接下来是一个长度为 n 且仅包含字符 '0' 和 '1' 的字符串。
输出
这个串的最长平衡子串的长度和最长平衡子序列的长度，两者之间用空格隔开，最后换行。

样例输入
8
01001001
样例输出
4 6

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

int n;
string s;
int sum;
int l[100001], r[100001], ans[100001];

int main()
{
cin >> n >> s;

Copy code
l[0] = 1;
sum = 0;
for (int i = 0; i < n; i++)
{
    sum += (s[i] == '1' ? 1 : -1);
    l[i + 1] = (sum == 0 ? 1 : 0);
}

r[n] = 1;
sum = 0;
for (int i = n - 1; i >= 0; i--)
{
    sum += (s[i] == '1' ? 1 : -1);
    r[i] = (sum == 0 ? 1 : 0);
}

int ans1 = 0, ans2 = 0;
for (int i = 0; i < n; i++)
    ans1 = max(ans1, l[i] + r[i + 1]);
for (int i = 0; i < n; i++)
    ans2 += (l[i] == 1 || r[i + 1] == 1);

cout << ans1 << " " << ans2 << endl;
}