LeetCode32:动态规划求解最长有效括号问题

在LeetCode的第32题中，任务是给定一个仅包含 '(' 和 ')' 的字符串，找到其中最长的有效括号子串的长度。例如，对于输入 ")()())"，输出应为4；而对于 "()(())"，输出应为6。

下面是一个基于动态规划的方法来解决这个问题的Java实现：

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

上述代码中，我们使用了一个动态规划数组 dp 来记录到当前位置为止的最长有效括号子串的长度。对于每一个字符，如果是右括号，则检查它是否能与前面的左括号匹配，并更新 dp 数组。最后，遍历整个字符串后，数组中的最大值即为所求的最长有效括号子串的长度。

为了验证这个方法的正确性，我们可以编写一些测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    String test1 = ")()())"; // 应输出 4
    String test2 = "()(())"; // 应输出 6
    System.out.println(solution.longestValidParentheses(test1));
    System.out.println(solution.longestValidParentheses(test2));
}

通过这些测试用例，我们可以看到该算法能够正确地计算出最长的有效括号子串的长度。