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的最长合法子串。子串必须是连续的。 思路：先用一个栈进行匹配，匹配成功的 ‘)’ 的对应的flag位置1，其余flag位置0。然后从后向前遍历，如果该位flag=1，则必须对应有一个’(‘与之匹配。wpp表示flag=1（flag=1表示该位是能匹配成功的 ‘)’）但是当前还未找到与之匹配的 ‘(’ ，这样的 ‘)’ 的个数。由于可以存在嵌套，所以在wpp等于0之前，可以接着出现flag=1的位，这种情况合法子串的长度加一。但是wpp等于0后紧接着的一位如果flag=0,则合法子串会断掉。cont（合法子串的长度）要重新开始计数。
（Runtime: 9 ms）
class Solution { public: int longestValidParentheses(string s) { stack<char> parentheses; int flag[s.length()]; memset(flag,0,sizeof(flag)); for(int i=0;i<s.length();){ if('('==s[i]){ parentheses.push('('); i++; }else{ while(s[i]==')'){ if(!parentheses.empty()){ if('('==parentheses.top()){ parentheses.pop(); flag[i]=1; } } i++; } } } int cont=0,nums=0,wpp=0; for(int i=s.length()-1;i>0;){ if(flag[i]==1){ cont++; wpp++; i--; }else{ int tem=wpp; while(tem--){ if(flag[i]==0){ wpp--; }else{ cont++; wpp++; tem+=2; } i--; } if(flag[i]==0){ if(nums<cont){ nums=cont; } cont=0; i--; } } } if(nums<cont){ nums=cont; } return nums*2; } };DP解法
代码