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.
思路：自己按照早上Scramble String (hard)★ 的动态规划方法试着做了一遍，‘（’表示为1， ‘）’表示为-1，用dp[start]记录不同长度情况下以start开始的括号对应的数字之和。如果为0则表示有效，更新最大长度。 结果超时了，说明我这个O(n2)的方法不行。
int longestValidParentheses(string s) {
string scpy = s;
int ans = ;
while(!scpy.empty() && scpy[] == ')') //跳过位于前面的 ) 因为肯定无法配对
{
scpy.erase(scpy.begin());
}
if(scpy.empty())
return ans;
vector<int> dp; //dp[start]
vector<int> dp1;
for(int start = ; start <= scpy.length() - ; start++)
{
dp.push_back((scpy[start] == '(') ? : -);
dp1.push_back(dp.back());
}
for(int len = ; len <= scpy.length(); len++)
{
for(int start = ; start <=scpy.length() - len; start++)
{
dp[start] = dp[start] + dp1[start + len - ];
if(dp[start] == && len > ans)
{
ans = len;
}
}
}
return ans;
}
大神可以通过而且简洁的O(n)方法
用longest[i]存储以 i 结尾时最大有效长度（必须包括第 i 个字符）
如果s[i] = '(' longest[i] = 0
else s[i] = ')'
If s[i-1] is '(', longest[i] = longest[i-2] + 2
Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]
the condition "s[i-1] == '('" since "s[i-longest[i-1]-1] == '('" actually concludes this case. We could just use "if (i-1>=0 && i-longest[i-1]-1 >=0 && s[i-longest[i-1]-1] == '(')"
int longestValidParentheses(string s) {
if(s.length() <= ) return ;
int curMax = ;
vector<int> longest(s.size(),);
for(int i=; i < s.length(); i++){
if(s[i] == ')' && i-longest[i-]- >= && s[i-longest[i-]-] == '('){
longest[i] = longest[i-] + + ((i-longest[i-]- >= )?longest[i-longest[i-]-]:);
curMax = max(longest[i],curMax);
}
}
return curMax;
}