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.
思路一：
首先从最基本的问题说起，遍历整个字符串，遍历到当前字符，我们计算以此字符为结束的括号匹配最长序列为多长，可以从当前字符到前面的所有字符组成字符串来进行判断，计算最终的结果是否比当前记录的结果长。等到遍历了所有的字符，也就知道这个字符中可匹配的括号序列的最大长度。
int check(string& str,int begin,int end){stack<char> st;int i;for(i = begin;i<=end;i++){if(str[i] ==')' &&(!st.empty() && st.top() =='('))st.pop();elsest.push(str[i]);}if(st.empty())return end-begin+1;elsereturn 0;}//也可以这么理解数列和为0的最长的序列 int Longest_dp(string& str){int i,j;int tmp;int max=0; int pos; for(i=0;i<str.size();i++){for(j=0;j<=i;j++)if((tmp = check(str,j,i))>max){max = tmp;break;}}return max;}思路二：用一个bool数组来标记已经匹配过的字符，找到最长的连续标记的长度就是所求的结果。只要遍历两遍数组，时间复杂度为O(n)。
int longestValidParentheses(string s) {bool *a = new bool[s.length()];memset(a, false, s.length());stack<int> st;for (int i = 0; i < s.length(); ++i) {if (s[i] == '(') {st.push(i);} else if (s[i] == ')' && !st.empty()) {a[i] = true;a[st.top()] = true;st.pop();}}int max_len = 0, cur_len = 0;for (int i = 0; i < s.length(); ++i) {if (a[i]) ++cur_len;else cur_len = 0;max_len = max(max_len, cur_len);}return max_len;}思路三：
如果我们使用栈记录某一个符号的在字符串的位置，假如对于当前字符和栈顶位置的字符可以匹配的，，那么可以根据栈是否为空来判断当前最长匹配子序列，然后和目标进行比较。
int longestValidParentheses(string s) {stack<int> st;int pos;int maxlen = 0;for(int i = 0 ; i < s.size() ; i++){if(s[i] == '(') st.push(i);else // ')'{if(!st.empty() && s[st.top()]=='('){st.pop();if(st.empty())pos = i+1;elsepos = i-st.top();if(maxlen < pos)maxlen = pos;}elsest.push(i);}}return maxlen;}
闲淡时光里徜徉书海。本文是旅游开心句子说说心情，希望对大家有帮助！
