1.栈

用栈保存最近未匹配括号的下标，将栈初始化为{-1}。 只有当前字符s[i]为')'且未匹配括号为'('时，弹出栈顶元素，并更新匹配括号子串的最大长度。 否则就将当前括号的下标进栈。

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        if(s.empty()) return 0;
        int n = s.size();
        stack<int> st;
        st.push(-1);
        int res = 0;

        for(int i = 0; i < n; i++){
            if(s[i] == ')' && !s.empty() && s[st.top()] == '('){
                st.pop();
                res = max(res, i - st.top());
            }else{
                st.push(i);
            }
        }
        return res;
    }
};

2.动态规划

用dp[i]保存s[0...i]这个字符串的最长匹配括号。

当s[i]为左括号时，dp[i] = 0;

只有当s[i]为右括号')', i-1前面的最长匹配部分的前一个位置 i-dp[i-1]-1为'(', 对dp[i]进行更新:

dp[i] = dp[i-1] + 2 + dp[i - dp[i-1]- 2]

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        if(s.empty()) return 0;
        int n = s.size();
        vector<int> dp(n);
        int res = 0;
        for(int i = 1; i < n; i++){
            if(s[i] == ')' &&  i- dp[i-1] > 0 && s[i - dp[i-1] - 1] == '('){
                dp[i] = dp[i-1] + 2;
                if(i-dp[i-1]-2 >= 0){
                    dp[i] += dp[i-dp[i-1]-2];
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};