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