# 最长有效括号

Posted: 09.18.2019

# 描述

# 算法

dp[i]: 在位置 i 结束的，最长的有效括号
并且从 0 ~ i 位置开始的最长有效括号，而是只考虑 i
这一点很重要，一定要先理解了才行

• 从 0 开始一直遍历到 n
  • 如果碰见了 (，在当前位置结束的括号，不可能是有效的，因此设置 dp[i] = 0
  • 如果碰见了 )
    • 如果碰见的是 ()，那么当前最长有效括号取决于位置在 i - 2 的最长有效括号，dp[i] = d[i - 2] + 2
    • 如果碰见的是 ))
      • 我们需要查看位于 (i - 1 - dp[i - 1]) 的字符，为什么是这个位置呢？
        • i - 1 是当前字符的前一个字符，dp [i - 1] 为结束在前一个字符的，最长有效括号
        • (i - 1 - dp[i - 1]) 代表了：在前一个字符的位置，减去其对应的最长有效括号
        • 因此，s[i - 1 - dp[i - 1]] 位置的字符，是与当前 s[i] 字符所对应的字符
      • 如果该字符为 (，这就说明这个位置的字符可以和当前的字符配对起来
        • 也就是说，从该字符（假如说位置为 index）一直到当前字符的括号，都是有效的
        • 这一段的距离是 dp[i - 1] + 2，因此我们可以在前面最长有效括号的基础上，加上这段距离
        • 而在 index 这个位置之前，最长的有效括号为 dp[i - 2 - dp[i - 1]]
        • 因此，我们最终所得到的最长有效括号为 dp[i] = dp[i - 1] + dp[i - 2 - dp[i - 1]] + 2
      • 如果该字符为 )，那么就说明该字符无法和当前的字符配对
        • 因此，从 index 到 i 这段，我们无法形成一段在 i 结束的有效字符
        • 因此，我们需要设置 dp[i] = 0

# 代码

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    if (!s) return 0;
    
    const dp = [0];
    
    for (let i = 1; i < s.length; i++) {
        // 只有当碰见 ( 时，才开始检查
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                dp[i] = (dp[i - 2] || 0) + 2;
            } else {
                if (s[i - dp[i - 1] - 1] === '(') {
                    dp[i] = dp[i - 1] + 
                            (dp[i - 2 - dp[i - 1]] || 0) + 2;
                } else {
                    dp[i] = 0;
                }
            }
        } else {
            dp[i] = 0;
        }
    }
    
    return Math.max.apply(Math, dp);
};