32-longest-valid-parentheses.md

32. Longest Valid Parentheses - 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

---

题目标签：String / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	4 ms	9.6 MB

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> dp(n);
        int t, res = 0;
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (c == ')') {
                if (i && s[i - 1] == '(') {
                    dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
                } else if (i > 1 && (t = i - dp[i - 1] - 1) >= 0 && t < n && s[t] == '(') {
                    dp[i] = (t > 1 ? dp[t - 1] : 0) + dp[i - 1] + 2;
                }
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();