算法-面试题系列(一)➡️题目三➡️子串最长括号有效配对

括号有效配对是指:

1. 任何一个左括号都能找到和其正确配对的右括号
2. 任何一个右括号都能找到和其正确配对的左括号

给定一个字符串，返回一个括号字符串中，最长的括号有效子串的长度。

题解思路：

定义一个数组,子串中，以index为结尾，最长的有效配对长度为Len;

image-20210513213753516

image-20210513214338699

• 求dp[3]的答案分析

image-20210513215213572

image-20210513215730595

image-20210513221157299

image-20210513221506618

public static int maxLength(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] dp = new int[str.length];
        int pre = 0;
        int ans = 0;
        // dp[0] = 0;
        for (int i = 1; i < str.length; i++) {
            if (str[i] == ')') {
                pre = i - dp[i - 1] - 1; // 与str[i]配对的左括号的位置 pre
                if (pre >= 0 && str[pre] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }