最长有效括号

题目

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

示例 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<int> 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;
    }
};