题目描述
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示：
0<=s.length<=3∗1040 <= s.length <= 3 * 10^40<=s.length<=3∗104
s[i] 为 ‘(’ 或 ‘)’
思路
使用动态规划，考虑以每个位置结尾的答案最大值。具体的步骤见代码。
代码
classSolution{public:intlongestValidParentheses(string s){intn=s.length();vector<int>dp(n);// 以i结尾的答案最大值intres=0;for(inti=0;i<n;++i){// (结尾的不是答案if(s[i]==')'){// 上一个是(, 直接合并if(i>0&&s[i-1]=='('){dp[i]=(i>=2?dp[i-2]:0)+2;}// 上一个是), 看看上一个合并的前一个数不是(, 是的话可以合并elseif(i>0&&s[i-1]==')'&&i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-1]+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0)+2;}}res=max(res,dp[i]);}returnres;}};
