# Longest Valid Parentheses    ## Intuition

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.

1. The simplest case is that s[i] == '('. In this case, dp[i] = 0.
2. If s[i] == ')', let's discuss 2 differnet cases.
• If s[i - 1] == '(', like ....)(). Then dp[i] = dp[i - 2] + 2.
• If s[i - 1] == ')', list ....(()) then we need to come to the previous character of the longest valid substring end with i - 1, and see if it is a (. If so, then dp[i] = dp[i - 1] + 2 + dp[prev - 1].

## Solution

``````
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp =  * (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)

``````