32.最长有效括号

官方题解

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        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;
                } 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;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这题目当时看了好久才看懂...当时以为下面式子 结果为 4，其实是2

()(() ==> 2

求 最长、连续 且 有效 的字符串长度

使用 Carl 哥的动态规划五部曲求解， 动态五部曲 - 代码随想录

1、dp[i] 的含义

​ dp[i]：i 元素能够 与 前面元素 组成的最长、连续且有效的字符串长度（局部，不是代表 前面所有字符串中的最长、连续且有效的字符串长度），'(' ==> dp[i] =0

2、递推公式

if sc[i] == ')' 
    if sc[i - 1] == '('    // ( ) 两两成对，注意 ()() ==> 4
        dp[i] = dp[i - 2] + 2
    if dp[i - 1] == ')'    // 检查是否是 (( ))，((( )))...
        //这时候需要往前挪 i - dp[i] 然后再挪一格 判断是否是 '('，dp[i] 表示 i 与前面元素组成的合法字符串长度
        if sc[i - dp[i - 1] - 1] == '('
        dp[i] = dp[i - 1]    //延续前面香火
                + dp[i - dp[i - 1] - 2]  + 2  //类比 if dp[i - 1] == '('，dp[i] = dp[i - 2] + 2

3、初始化

4、确定遍历顺序

5、距离推导dp数组

例如

String	（	）	）	（	（	（	）	）	）
i
dp[i]

看了官方题解后，尝试着自己编程实现

// 错误题解
class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;

        char[] sc = s.toCharArray();
        int[] dp = new int[sc.length];
        int max = 0;
        for (int i = 1; i < sc.length; i++) {
            if (sc[i] == ')') {
                if (sc[i - 1] == '(') dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
                //这里可以去掉外层 if
                if (sc[i - 1] == ')') {
                    //这里 if 语句有问题
                    // if (i - dp[i - 1] > 0 && sc[i - dp[i - 1] - 1] == '(')
                    if (i - dp[i - 1] - 1 > 0 && sc[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 > 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                }
            }
            if (max < dp[i]) max = dp[i];
        }
        return max;
    }
}