题解 | 最长的括号子串

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> dp(n, 0);   // 以i为结尾的最大匹配长度
        dp[0] = 0;  // 自己单独一个括号肯定无法匹配

        int res = 0;
        for(int i=1; i<n; i++){
            if(s[i]=='(')
                dp[i] = 0;
            else{
                if(s[i-1]==')' && i-1-dp[i-1]>=0 && s[i-1-dp[i-1]]=='('){
                    if(i-2-dp[i-1]<0)
                        dp[i] = dp[i-1] + 2;
                    else
                        dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]];
                }
                else if(s[i-1]=='(' && i-2<0)
                    dp[i] = 2;
                else if(s[i-1]=='(' && i-2>=0)
                    dp[i] = dp[i-2] + 2;
                else
                    dp[i] = 0;
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

分几种情况：

1、以'('结尾：不用想了以‘（’结尾字符串不可能合法；

2、以‘）’结尾：合法的几种情况如下：

2.1：...()：则i能与i-1匹配上，则如果i-2存在，dp[i]=dp[i-2]+2；

2.2：(...))：比如，dp[i-1]=2，则如果i-2-1的位置是个（，正好能匹配上，则dp[i]=dp[i-1]+2；即"(....)"这种情况

2.3：()(...))：2.2的延伸。如果2.2匹配完之后，发现整个的左边还有东西，则需要再加上dp[i-2-1-1]。