题目
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;
}
};
思考二
虽然这道题理解了，但是如果要我自己想，我还是不知道怎么把这个想出来。得继续摸索要，看来未来很长时间内要继续拍脑瓜了。
