Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"Example 2:
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"题目：最长的有效括号对。
思路：动态规划。参考。对于前i个元素组成的子串，我们把包含s[i]在内的的最长有效括号对的长度记为dp[i]，那么如果s[i]==（，显然dp[i]=0；如果s[i]==)，那么dp[i]可以根据s[i-1]来更新状态：
s[i-1]=(，此时dp[i-1]=0，dp[i]=dp[i-2]+2s[i-1]=)，此时s[i]应匹配到上一个未匹配的(，因为s[i-1]匹配长度为dp[i-1]，因此s[i]匹配至s[j] = s[i-1-dp[i-1]]，如果s[j]=(，那么dp[i] = dp[i-1]+2+dp[j-1]。工程代码下载
class Solution { public: int longestValidParentheses(string s) { int n = s.size(); if(n == 0) return 0; vector<int> dp(n); int res = 0; for(int i = 1; i < n; ++i){ if(s[i] == ')'){ if(s[i-1] == '('){ dp[i] = (i-2) >=0 ? dp[i-2] + 2 : 2; } else if(s[i-1] == ')'){ int j = i - 1 - dp[i-1]; if(j >=0 && s[j] == '(') dp[i] = (j-1) >= 0 ? dp[i-1] + 2 + dp[j-1] : dp[i-1] + 2; } res = max(res, dp[i]); } } return res; } };方法2：栈。参考Discuss。当右括号数超过左括号数时，括号对无效，记录下这次失效的位置i，当遇到下一个失效的位置j时，我们知道i到j之间的括号是匹对上的，更新有效括号的最大长度。具体实现代码参考使用了一些技巧，初始失效位置设置为-1，当遇到右括号时，将上一个左括号（存放的是下标）弹出，如果栈变为空，说明右括号个数已经大于左括号数了，则需要更新失效位置（设置为当前右括号对应的下标），如果栈未空，则说明栈顶中对应的左括号到当前右括号是配对的。
class Solution { public: int longestValidParentheses(string s) { int n = s.size(); stack<int> sk; sk.push(-1); int res = 0; for(int i = 0; i < n; ++i){ if(s[i] == '(') sk.push(i); else{ sk.pop(); if(sk.empty()) sk.push(i); else res = max(res, i - sk.top()); } } return res; } };