class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if not s: return 0
pleft = 0
pmax = 0
dp = [0]*len(s)
for i in range(len(s)):
if s[i] == '(':
dp[i] = 0
pleft+=1
else:
if pleft < 1:dp[i] = 0
else:
pleft=1
dp[i] = 2 + dp[i1] + dp[i2dp[i1]]
pmax = max(pmax,dp[i])
return pmax
Python DP O(n) without stack


Thanks for sharing your solution @xuhongnever. Would you explain your logic behind the line
dp[i] = 2 + dp[i1] + dp[i2dp[i1]]
?

@pg2286 Thank you for viewing my answer !
The current Parentheses string can be divided into three parts **part 1**(**part 2**), the two parentheses is part 3
So the current string length should Part 3 : 2 + part 2: dp[i1] + part 1 : dp[i2dp[i1]].