题解 | #最长的括号子串#

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        vector<int> dp(s.size(), 0); // 记录最大合法字符串的长度
        int maxValue = 0;
        // 一共两种情况(())和()()合法，需要进行区分
        for(int i = 0; i < s.size(); i++) {
            // 令元素为‘（’的dp值都为0，只考虑元素为‘）’的情况
            if(s[i] == ')') {
                int prev = i - 1 - dp[i - 1]; // prev为以i-1结尾的合法字符串的开始下标
                if(prev >= 0 && s[prev] == '(') {
                    dp[i] = dp[i - 1] + 2; // 考虑(())情况
                    if(prev - 1 >= 0) // 考虑()()情况
                        dp[i] += dp[prev - 1];
                }
            }
            maxValue = max(maxValue, dp[i]);
        }
        return maxValue;
    }
};