题目：
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.
思路：
这道题可以用一维动态规划逆向求解。维护一个长度与string长度相同的一维数组dp，数组元素初始化为0.dp[i]表示从s[i]到s[s.length()-1]的最长有效匹配子串长度，那么dp[s.length()-1] = 0;然后从(n-2)到0逆向求dp，并记录其最大值。如果s[i] == ‘（’，则在s中从i到s.length()-1计算dp[i]的值，这个计算要分两步走：第一步在s中寻找i+1开始的有效匹配子串长度，即dp[i+1]，跳过这段有效的括号子串，查看下一个字符，位置为j = i + dp[i+1] + 1。若j没有越界并且s[j] == ')'，则s[i......j]为有效括号匹配，dp[i] = dp[i+1] + 2。第二步在求得了s[i......j]的有效匹配长度之后，若j + 1没有越界，则dp[i]的值还要加上j+1开始的最长有效匹配。即d[i] += dp[j+1]
代码：
C++实现
class Solution { public: int longestValidParentheses(string s) { int i,j,n; int max=0; n=s.length(); int dp[65536]; for(i=0;i<n;i++) dp[i]=0; for(i=n-2;i>=0;i--) { if(s[i]=='(') { j=i+1+dp[i+1]; if(j<n && s[j]==')'){ dp[i]=dp[i+1]+2; if(j+1<n) dp[i]+=dp[j+1]; } } if(max<=dp[i]) max=dp[i]; } return max; } };思路2：
可以使用栈来实现，将字符串从头至尾遍历，如果字符为‘（’将其压入栈中，否则，如果栈部位空而且栈顶元素为‘（’的话，说明至少可以组成一个‘()’的子序列，所以将栈顶元素弹出，此时，如果栈空了，说明i处的‘)’与之前所有的元素共同构成了一个子串，所以此串的长度为i+1。如果栈不为空，那么现在构成的子串长度为i减去栈顶元素的索引值。然后将求出的子串长度与原有最大长度比较并更新。如果栈顶元素为')'或者栈空，那么将')'压入栈中。遍历一遍即可求出最大子串。
代码：
C++实现
class Solution { public: int longestValidParentheses(string s) { stack<pair<int, char>> stk; int maxLen = 0; int n = s.length(); for (int i = 0; i < n; i ++){ if (s[i] == '(') stk.push(pair<int,char>(i,'(')); else{ if(!stk.empty() && stk.top().second == '('){ int curLen = 0; stk.pop(); if(stk.empty()) curLen = i + 1; else curLen = i - stk.top().first; maxLen = max(maxLen,curLen); } else stk.push(pair<int, char>(i, ')')); } } return maxLen; } };