题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

分析

一开始的思路是模拟。用模拟的做法主要的问题是复杂，而且容易忽视一些边界情况。在经历了N次的WA+修改之后，我的代码终于AC了。我为我的这种精神感动。
总结一些这种做法的思路：

• 从左往右遍历字符串
• 记录每个合法子串开始的位置
• 记录尚未配对的"("的位置
• 记录当前合法子串的长度
• 若合法子串结束，取以下长度的最大值：
  1.出现")"且没有尚未匹配的"("时，取得当前合法子串长度；
  2.字符串到达末尾，取末尾位置与最后一个未匹配的"("之间的长度，以及未匹配的"("两两之间的长度，以及上一个合法子串串开始的位置和最左侧的未匹配"("之间的长度。

实现一

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans=0, len=0, sl=s.size(), last=-1;
        stack<int> stk;
        for(int i=0; i<s.size(); i++){
            if(s[i]=='('){
                stk.push(i);
                len++;
            }
            else if(!stk.empty()){
                stk.pop();
                len++;
            }
            else{
                ans = max(ans, len);
                len = 0;
                last=i;
            }
        }
        if(!stk.empty()){
            int p = stk.top(), q=p;
            stk.pop();
            ans = max(ans, sl-p-1);
            while(!stk.empty()){
                q = stk.top();
                ans = max(ans, p-q-1);
                
                p = q;
                stk.pop();
            }
            ans = max(ans, q-last-1);
        }
        else{
            ans = max(ans, len);
        }
        return ans;
    }
};

思考一

这题虽然这样做出来了，但是感觉这种做法给自己带来的提升不大。一是真正面试的时候不会有这么多时间让我想，二是到时候也没有机会让我一次次地拟合测试数据，三是这种做法有时候需要一拍脑袋得到，也挺看状态和运气的。
看到题解中还有用dp的方法，所以从这个角度思考做法。我觉得dp主要问题是寻找能够具有无后效性的量，但是目前我还没有找到什么有效方法，主要靠拍脑瓜，或者看答案=_=
这题中，我已开始想选择使用dp[i]代表s.substr(0, i)中的最大合法括号长度，但很快发现需要很多补充条件。后来看了题解才知道dp[i]代表以s[i]为结尾的最大合法括号长度比较好，因为最长子串的位置在这题里确实是很重要的因素。

实现二

class Solution {
public:
    int longestValidParentheses(string s) {
        int sl=s.size(), ans=0;
        vector<int> dp(sl, 0);
        for(int i=1; i<sl; i++){
            int match = i - dp[i-1] -1; 
            if(s[i]==')' && match>=0 && s[match]=='('){
                dp[i] = dp[i-1] + 2;
                if(match>=1)
                    dp[i] += dp[match-1];
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

思考二

虽然这道题理解了，但是如果要我自己想，我还是不知道怎么把这个想出来。得继续摸索要，看来未来很长时间内要继续拍脑瓜了。