LeetCode 32. 最长有效括号***

两种方法，DP以及栈版本；

两种正解自己都没整出来，栈局限于匹配，额外记录，但是会发现当无法判断出“()()((()”后半段的情况；

栈内放置上一位不能匹配的右括号；

如果当前能有匹配序列，则该不能匹配的右括号必定在栈底；

如果出现新的不能匹配的右括号，则替换栈底，压栈；

如果当前发现能匹配，出栈，计算i-st.top()，获得当前能够匹配序列距离不能匹配的右括号的距离，视之为长度；

DP则像是子问题的划分；

一维dp数组，数组内第i为代表当其为右括号的时候的最长距离；

如果是左括号，直接为零；

DP方程如上；

唯一要注意的是，dp[i-dp[i-1]-2]是怎么来的；

如果是连续括号"()((()))"；

则如果计算后半部分算完后，必须要加上前面的"()"，从而得出整个序列的长度；

而前面的"()"也已经算到过；

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0, n = s.length();
        vector dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = max(maxans, dp[i]);
            }
        }
        return maxans;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        stackst;
        int cnt=0;
        st.push(-1);
        for(int i=0;i
            if(s[i]=='(')
                st.push(i);
            else if(s[i]==')'){
                st.pop();
                if(st.empty()){
                    st.push(i);
                }else{
                    cnt=max(cnt,i-st.top());
                }
            }
        }
        return cnt;
    }
};