最长有效括号

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.empty()) return 0;

        int n = s.length();
        vector<int> dp(n);
        dp[0] = 0;
        int res = 0;

        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                int pos = i - 1 - dp[i - 1];
                if (pos >= 0 && s[pos] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pos - 1 >= 0 ? dp[pos - 1] : 0);
                }
            }
            res = max(res, dp[i]);
        }

        return res;
    }
};