This problem is one of the hardest dynamic programming problems.
Let's define a dp array first. dp[i] indicates the longest valid parentheses that ends at i. Now let's discuss how to get dp[i], if dp[k] for any k that k < i has been calculated.
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp = [0] * (len(s) + 1)
for i, c in enumerate(s):
if c == '(' or i == 0:
continue
if s[i - 1] == '(':
dp[i] = 2 if i <= 2 else dp[i - 2] + 2
else:
prev = i - 1 - dp[i - 1]
if prev >= 0 and s[prev] == '(':
dp[i] = dp[i - 1] + 2
if prev - 1 > 0 and s[prev - 1] == ')':
dp[i] += dp[prev - 1]
return max(dp)