```
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
dp = [0 for _ in range(len(s) + 1)]
for i, c in enumerate(s):
if c == '(':
dp[i + 1] = 0
stack.append(c)
else:
dp[i + 1]=dp[i] + 2 if stack and stack.pop() == '(' else 0
if i + 1 - dp[i + 1] > 0:
dp [i + 1] += dp [i + 1 - dp [i + 1]]
return max(dp)
```