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

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        int res=0;
        //int dp[s.size()];
        vector<int> dp(s.size(),0);
        int pre=0;
        for(int i=1;i<s.size();i++){
            if(s[i]==')'){
                pre=i-dp[i-1]-1;//记录此时'('对应最近的左边位置，并判断是否匹配为'('
                if(pre>=0&&s[pre]=='('){//pre可能为负值（没有可匹配的位置），此时会越界没有判断的意义
                    dp[i]=dp[i-1]+2+(pre>0?dp[pre-1]:0);//前一位置的长度+2并判断是否能能连接更前面的括号
                }
            }
            res=max(res,dp[i]);
        }
        //不能返回dp[s.size()-1],因为上述代码只在有')'时才dp[i]才进行更新，若最后一位为'('返回的答案是错误的
        return res;
    }
};