动态规划：
class Solution { public: int longestValidParentheses(string s) { int maxans = 0, n = s.length(); vector<int> 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) { stack<int> st; int maxn = 0,start = -1; for(int i = 0;i < s.size();i++){ if(s[i] == '('){ st.push(i); } else{ if(st.empty()){ start = i; } else{ st.pop(); if(st.empty()){ maxn = max(maxn,i-start); } else{ maxn = max(maxn,i-st.top()); } } } } return maxn; } }; class Solution { public: int longestValidParentheses(string s) { stack<int> st; vector<bool> mark(s.length()); for(int i = 0; i < mark.size(); i++) mark[i] = 0; int left = 0, len = 0, ans = 0; for(int i = 0; i < s.length(); i++) { if(s[i] == '(') st.push(i); else { // 多余的右括号是不需要的，标记 if(st.empty()) mark[i] = 1; else st.pop(); } } // 未匹配的左括号是不需要的，标记 while(!st.empty()) { mark[st.top()] = 1; st.pop(); } // 寻找标记与标记之间的最大长度 for(int i = 0; i < s.length(); i++) { if(mark[i]) { len = 0; continue; } len++; ans = max(ans, len); } return ans; } };