E29952 咒语序列

思路：

• 考虑对每个位置 $i$，可能存在一个最大的 $j\le i$，使得 $[j,i]$ 为一个合法括号序列，如 ()(()) 中 $i=6$ 对应的最大的 $j$ 为 $3$，$i=4$ 时不存在这样的 $j$。
• 考虑 dp：设 $d{p}_i$ 表示 $s[1,i]$ 的最长合法后缀括号序列。
• 从前到后扫一遍，维护一个栈，当 $s_i$ 为 ( 时将 $i$ 压入，当 $s_i$ 为 ) 时，若栈非空则 $j$ 为栈顶下标，然后弹栈，此时更新 $d{p}_i=d{p}_{j-1}+(i-j+1)$。
• 答案即为 $max(d{p}_i)$。时间复杂度为 $O(n)$。
• 如上面的例子中，$d{p}_2=d{p}_0+2=2,d{p}_5=d{p}_3+2=2,d{p}_6=d{p}_2+4=6$，答案为 $max(d{p}_2,d{p}_5,d{p}_6)=6$。

代码：

#include <iostream>
#include <stack>

using namespace std;

int dp[30001];
stack<int> stk;

int main(){
	int len, ans = 0;
	string s;
	cin >> s;
	len = s.size();
	s = " " + s;
	for (int i = 1; i <= len; i++){
		if (s[i] == '('){
			stk.push(i);
		} else {
			if (!stk.empty()){
				int cur = stk.top();
				stk.pop();
				dp[i] = dp[cur - 1] + (i - cur + 1);
				ans = max(ans, dp[i]);
			}
		}
	}
	cout << ans;
	return 0;
}