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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution {public: int longestValidParentheses(string s) { int len = s.size(); vector<int> dp(len,0); int max = 0; for(int i = 1; i < len; ++i){ if(s[i] == ‘)‘){ if(s[i-1] == ‘(‘){ dp[i] = (i>=2? dp[i-2]:0) + 2; } else{ if(i - dp[i-1] - 1>=0 && s[i - dp[i-1] - 1] == ‘(‘){ dp[i] = dp[i-1] + 2 + ((i - dp[i-1] - 2) > 0?dp[i - dp[i-1] - 2]: 0); } }//--end of else }//--end of if max = max < dp[i]? dp[i]: max; }//--end of for return max; }}; |
原文：http://www.cnblogs.com/zhxshseu/p/15d8ea4859752b1464fbfe2419856ae6.html