求一段由括号组成序列中最长的合法的括号序列，(lenleq 10^5)。
解
显然想到栈，于是从左往右扫描，从答案的角度看，合法括号序列部分必然是互不交叉的且连续的，而且内部也是合法的，那么其他部分都是不合法的，我们只要能设法找到这些部分。
如果从左往右扫描到了多余的右括号，则说明后面无论是什么字符都是不合法的，于是另外起一段开始扫描，如果扫到到合法的右括号，前面必然有一个位置放左括号，而且这两个括号间的序列都是合法的。
于是我们可以想到这样一个算法，维护一个栈，保存字符以及其所在的位置，从左往右扫描，如果遇到不合法的如多余的右括号，就清空栈，否则标记这两个括号的位置，表示这两个位置是合法的，又根据上面的阐述，容易知道两个位置之间的位置也是合法的，最后问题就转化为求一段01序列中最长的连续的1的长度，时间复杂度(O(n))。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define Size 105000
using namespace std;
bool check[Size];
char s[Size],za[Size],dz[Size];
int n,zb[Size],tz,ans;
int main(){
dz[')']='(',dz[']']='[',dz['}']='{';
scanf("%s",s+1),n=strlen(s+1);
for(int i(1);i<=n;++i){
if(dz[s[i]])
if(dz[s[i]]==za[tz])
check[i]=check[zb[tz]]=true,--tz;
else tz=0;
else za[++tz]=s[i],zb[tz]=i;
}
for(int i(1),j;i<=n;++i){
if(!check[i])continue;
for(j=i;j<=n;++j)
if(!check[j])break;
else check[j]^=check[j];
ans=max(ans,j-i);
}printf("%d",ans);
return 0;
}