Longest Valid Parentheses(动态规划)
Longest Valid Parentheses
更多技术博客 http://vilins.top/
题目
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
Example 2:
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
分析
在这里我们用一个longest_curr数组去保存当前下标前连续匹配的括号的数量，注意这里是连续出现的括号。
接下来我们需要找出状态转移方程，当字符串的字符为’)‘时可能意味着状态的改变，所以我们的判断条件是在’)‘时进行的。
具体来说，在下标i之前的longest_curr值都已经被求出来了，那么对于下标为并且是’)'的字符，有如下状态转移方程：
longest_curr[i] = longest_curr[i - longest_curr[i-1] - 2] + 2 + longest_curr[i-1];longest_curr[i - longest_curr[i-1] - 2]是指在这个整体匹配之前已经匹配的字符数量，
longest_curr[i-1]指存在这样的情况“()(())"，longest_curr[i-1]指计算（（）），这个符合中间的这两个。
最后需要考虑的一点就是下标的界限问题。
源码
class Solution { public: int longestValidParentheses(string s) { int size = s.size(); int max_num = 0; vector<int> longest_curr(size, 0); if(s.size() <= 1) { return 0; } for(int i =1; i < size; i++) { if(s[i] == ')' && ((i - longest_curr[i-1] - 1) >= 0) && s[i - longest_curr[i-1] - 1] == '(') { if(i - longest_curr[i-1] - 2 >= 0) { longest_curr[i] = longest_curr[i - longest_curr[i-1] - 2] + 2 + longest_curr[i-1]; } else { longest_curr[i] = 2 + longest_curr[i-1]; } max_num = max(max_num, longest_curr[i]); } } return max_num; } };