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

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        //长度为0的串，返回0
        if(s.length() == 0) 
            return res;
        //dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        vector<int> dp(s.length(), 0); 
        //第一位不管是左括号还是右括号都是0，因此不用管
        for(int i = 1; i < s.length(); i++){ 
            //取到左括号记为0，有右括号才合法
            if(s[i] == ')'){ 
                //情况一：如果该右括号前一位就是左括号
                if(s[i - 1] == '(') 
                    //计数+2
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 
                //情况二：找到这一段连续合法括号序列前第一个左括号做匹配
                // 如果 ()) 则 i - dp[i - 1] == 0
                // i - dp[i - 1] > 0 说明i-1为 右括号，且i-1属于一段合法序列，其长度为dp[i-1],如()()(()) i==7时,dp[6]=2; 
                // i-dp[i-1]-1为前一段合法序列再前一个元素下标,即与 i 对应的下标；
                else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') 
                    // dp[i - 1] > 1 说明dp[i-1]为合法序列，情况为()()(());
                    // dp[i - 1] <= 1 说明dp[i-1]为合法序列，情况为()(),i=3时，dp[2]=2，则相减结果为1; ())，i=3时，dp[2]=2, i-dp[i-1]为0;

                    // i - dp[i - 1] > 1 ，此处先执行i-dp[i-1],再判断结果是否>1;
                    
                    // 则dp[i - dp[i - 1] - 2]为dp[i-1]这段合法序列长度的再前两个位置的dp值，注意i - dp[i - 1] - 1是跟当前 i对应的左括号， 该位置再-1则为对应左括号前一位；
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            //维护最大值
            res = max(res, dp[i]); 
        }
        return res;
    }
};


// class Solution {
// public:
//     int longestValidParentheses(string s) {
//         int res = 0;
//         //记录上一次连续括号结束的位置
//         int start = -1; 
//         stack<int> st;
//         for(int i = 0; i < s.length(); i++){
//             //左括号入栈
//             if(s[i] == '(') 
//                 st.push(i);
//             //右括号
//             else{ 
//                 //如果右括号时栈为空，不合法，设置为结束位置
//                 if(st.empty()) 
//                     start = i;
//                 else{
//                     //弹出左括号
//                     st.pop(); 
//                     //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
//                     if(!st.empty()) 
//                         res = max(res, i - st.top());
//                     //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
//                     else 
//                         res = max(res, i - start);
//                 }
//             }
//         }
//         return res;
//     }
// };