1. 情况一：找到字符串形如 “……()”，找到（）的前一个位置，所以 dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
2. 情况二：找到字符串形如 “((……))”，找到子串“((……))” 前的第一个位置 i - dp[i - 1] - 2，所以 dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;

class Solution {
    public int longestValidParentheses(String s) {
        int result = 0; // 用于记录最长有效括号子串的长度
        int[] dp = new int[s.length() + 1]; // dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度
        dp[0] = 0; // 初始化，第 0 个字符的最长有效括号子串长度为 0
        // 从第一个字符开始遍历到倒数第二个字符
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') { // 当前字符为 ')'
                //情况一：字符串形如 “……()”
                if (s.charAt(i - 1) == '(') { // 前一个字符是 '('，形成了有效括号对 "()"
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; // 更新当前字符结尾的最长有效子串长度为前一个字符的最长子串长度加上 2
                } //情况二：字符串形如 “……))”
                else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { // 前一个字符是 ')'，并且其前面有有效括号子串
                    // 判断当前字符前面一个有效括号子串的前一个字符是否是 '('，如果是则更新当前字符结尾的最长有效括号子串长度
                    //i - dp[i - 1] - 2是子串“((……))”前的一个位置
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                result = Math.max(result, dp[i]); // 更新最长有效括号子串的长度
            }          
        }
        return result; // 返回最长有效括号子串的长度
    }
}

• 时间复杂度分析：O(n)，其中 n为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。