public int longestValidParentheses2(String s) {
        int[] dp = new int[s.length()];
        int max = 0;
        for(int i = s.length() - 2; i >= 0; i--){
            if(s.charAt(i) == '('){
                int j = i + dp[i + 1] + 1;
                if(j < s.length() && s.charAt(j) == ')'){
                    dp[i] = dp[i + 1] + 2;
                    if(j + 1 < s.length()) dp[i] += dp[j + 1];
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }