class Solution {
    // 动态规划
    // dp[i] 代表以i结尾的最长有效括号子串的长度
    // s.charAt(i) == '( dp[i] = 0;
    // s.charAt(i) == ')' s.charAt(i - 1) = '(' dp[i] = dp[i - 2] + 2
    // if (i - dp[i - 1] - 2 >= 0)s.charAt(i - dp[i - 1] - 1) == '(' dp[i] = dp[i-1] + 2 + dp[i - dp[i - 1] - 2]
    // 初始化dp[0] = 0;
    // 遍历顺序 从左向右
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len];
        int maxLen = 0;
        for (int i = 1; i <= len - 1; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i-1) == '(') {
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                    maxLen = Math.max(maxLen,dp[i]);
                } else if (i-1 >= dp[i-1] && dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') { // 需要判断dp[i-1] > 0
                    dp[i] = (i - dp[i-1] >= 2)? dp[i-1] + dp[i-dp[i-1]-2] + 2 : dp[i-1] + 2;
                }
                 maxLen = Math.max(dp[i],maxLen);
            }
        }
        return maxLen;
    }
}