解题思路
给定只含 (、)、* 的字符串，题意要求：在某个连续子串中，把所有 * 全部忽略（删除）后，剩下的括号序列必须是有效括号串。于是可将问题转化为：
-
先把整串中过滤出所有括号，得到只含 (、) 的序列 par，并记录这些括号在原串中的位置数组 pos。
-
在 par 上求“最长有效括号”（经典 LVP）——可用 O(n) DP：
- 设
dp[i] 表示以 i 位置结尾的最长有效括号长度（单位：括号个数），若 par[i] == ')' 且与其匹配的左括号在 j = i - 1 - dp[i-1] 且 par[j] == '('，则
dp[i] = dp[i-1] + 2 (+ dp[j-1] 若 j-1 >= 0).
P4458.第1题-多多最长子串
题目内容
多多最近在处理一个字符串问题，该字符串由 '('、')' 和 '∗' 组成，多多希望找到最长的连续子串，使得当忽略所有 '∗' 后，该子串是一个有效的括号子串。
有效括号子串需满足：
- 括号成对闭合：每个 '(' 都有一个对应的 ')'
- 正确嵌套顺序：右括号不能出现在对应的左括号之前
输入描述
第一行输入为一个整数 T, 表示测试用例的组数 (1<=T<=100)
接下来 T 组数据，每组测试用例包含两行:
第一行输入为一个整数 N , 表示字符串的总长度 (1<=N<=500,000)
第二行输入为一个长度为 N 字符串，字符串由 ( 和 ) 以及 ∗ 组成
输出描述
输出包含 T 行
每一输出为一个整数，满足要求的最长的连续子串的长度
补充说明
空字符串是有效括号子串
样例1
输入
3
8
*(*(**))
4
(()*
8
*(()(*)*
输出
8
3
6
样例2
输入
2
4
****
4
)))(
输出
4
0
