LeetCode 32. 最长有效括号
原题链接
困难
作者:
linux_2019
,
2019-05-14 10:56:57
,
所有人可见
,
阅读 1187
class Solution {
public:
int longestValidParentheses(string s) {
int ant=0;
vector<int> dp(s.size(),0);
if(s.size()==0)
return 0;
int i;
dp[0]=0;
if(s.size()>=2)
if(s[0]=='(' && s[1]==')')
{
dp[1]=2;
ant=2;
}
for(i=2;i<s.size();i++)
{
if(s[i]== ')')
{
if(s[i-1]=='(')
dp[i]=dp[i-2]+2;
else if (s[i-1]==')'&&(i-dp[i-1]-1)>=0 && s[(i-dp[i-1]-1)]=='(')
if ((i - dp[i - 1] - 2) >= 0)
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
else
dp[i] = dp[i - 1] + 2;
ant=max(ant,dp[i]);
}
}
return ant;
}
};