Longest Valid Parentheses
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.
设dp[i]表示从s[i]开始（包括s[i]），到达s[n-1]时，最长的有效括号对的长度。
如果s[i]=='('
我们需要检查j=dp[i+1]+i+1对应的s[j]位置的括号是否为")"，如果s[j]为')'则说明又组成了一对括号
故此时dp[i]=dp[i+1]+2
于此同时，我们还需要继续考虑dp[j+1]的值，如果j+1没有超出范围，则dp[i]=dp[i+1]+2+dp[j+1]
其他情况dp[i]=0;
class Solution {
public:
int longestValidParentheses(string s) {
int n=s.length();
if(n==) return ;
int *dp=new int[n];
dp[n-]=;
int result=;
for(int i=n-;i>=;i--)
{
if(s[i]=='(')
{
int j=dp[i+]+i+;
if(s[j]==')')
{
dp[i]=dp[i+]+;
if(j<n-) dp[i]+=dp[j+];
}
else
{
dp[i]=;
}
if(dp[i]>result)
{
result=dp[i];
}
}
else
{
dp[i]=;
}
}
delete [] dp;
return result;
}
};