Description
如果一个括号序列插入"+"和"1"后，可以得到一个正确的数学表达式，那么它被称为"合法"的。例如，序列"(())(
)"，"()"和"(()(()))"是合法的，但")("，"(()"和"(()))("不是合法的。 给出一个由"("和")"字符组成的字符串
。你要找出它最长的是合法括号序列的子串，也同样要找出最长子串的个数。100%的数据：读入的字符串长度小于
等于10^6
Input
Output
Sample Input
)()()(
Sample Output
4 1
sol:栈+dp
f[i]表示到位置i能够形成的最长合法括号序列的子串的长度。
依次处理读入的字符串序列，如果字符为“（”，进栈，如果是“）”，则与栈顶的左括号配对。
如i为正在处理右括号，栈顶为k（k>0)，则f[i]=f[k-1]+i-k+1.
最后扫一遍，求出所有能形成的最大子串长度及个数。
代码如下：
#include <cstdio> #include <cstring> #include <vector> #include <iostream> using namespace std; const int N=1000005; int n,tot; int f[N],Q[N]; char s[N]; void init() {int i; scanf("%s",s+1);//下标从1开始 n=strlen(s+1); } void dp() {int i,k; tot=0;//记录栈中元素个数 for (i=1;i<=n;i++) if (s[i]==‘(‘)//是左小括号 Q[++tot]=i; else if (tot>0) {k=Q[tot];//该")"与位置k的"("匹配 tot--; f[i]=f[k-1]+i-k+1;//f[i]表示到位置i能够形成的最长合法括号序列的子串的长度 } } void out() {int i,ans=0, cnt=1; for (i=1;i<=n;i++) {if (f[i]==ans) cnt++; if (f[i]>ans) {ans=f[i]; cnt=1; } } if (ans==0) cnt=1; printf("%d %d\n",ans,cnt); } int main() { init(); dp(); out(); return 0; }
原文：https://www.cnblogs.com/cutepota/p/13453749.html