[!info] related notes 动态规划 线性 DP

最长有效括号

题目链接：https://leetcode.cn/problems/longest-valid-parentheses/

状态

输入只包含左右圆括号。dp[i] 表示以 s[i] 结尾的最长连续有效子串长度，不是子序列长度，也不要求整个输入有效（见 有效括号）。

转移

只有当 s[i] === ')' 时，才可能形成有效括号。

分两种情况：

1. ...()：如果 s[i - 1] === '('
2. ...))：如果 s[i - 1] === ')'，就去找前一个有效串左边能不能接上一个 '('

第二种情况中，pre = i - dp[i - 1] - 1 跳过前一个有效串；若 s[pre] 为左括号，新长度还要接上 dp[pre - 1]。例如 ()(()) 需要把前面的 () 一起计入。

JavaScript

var longestValidParentheses = function(s) {
    const n = s.length;
    const dp = new Array(n).fill(0);
    let ans = 0;

    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else {
                const pre = i - dp[i - 1] - 1;
                if (pre >= 0 && s[pre] === '(') {
                    dp[i] = dp[i - 1] + 2 + (pre >= 1 ? dp[pre - 1] : 0);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
    }

    return ans;
};