最长有效括号

题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0
``` 

提示：

0 <= s.length <= 3 * 104 s[i] 为 '(' 或 ')'

###思路
定义dp[i]表示以字符s[i]结尾的有效子串的长度，这个长度包含字符s[i]。如果s[i] == '('，那么dp[i] = 0。
如果s[i] == ')',s[i-1]=='(',dp[i] = dp[i-2] + 2。如果s[i] == ')',s[i-1] == ')',假如i - dp[i-1] - 1位置为'(',则dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2

比如字符串`)()(()))`,对于位置6,s[6] == ')',s[5] == ')',s[i - dp[i-1] - 1] == '(',位置,dp[5] == 2,dp[2]==2, dp[6]=dp[6-1] + dp[6 - dp[6-1] - 2] + 2 = dp[5]+dp[6 - 2 - 2]+2= 2 + 2 + 2 = 6

对于位置7，s[7]==')',s[6]==')',位置 s[i - dp[i-1] - 1] == ')',所以dp[7] = 0;

答案为max(dp[0,s.length-1])

###代码

class Solution { public: int longestValidParentheses(string s) { int n = s.length(); vector dp(n,0); int ans = 0; for(int i = 1;i < n;i++) { if(s[i] == ')') { if (s[i-1] == '(') { dp[i] = (i > 1?dp[i-2]:0)+2; } else if(i - dp[i-1] > 0 && s[i-dp[i-1]-1] == '(') { dp[i] = dp[i-1] + (i-dp[i-1]>1?dp[i-dp[i-1]-2]:0)+2; } ans = max(ans,dp[i]); } } return ans; } };