# 32. 最长有效括号

[https://leetcode-cn.com/problems/longest-valid-parentheses/](https://leetcode-cn.com/problems/longest-valid-parentheses/)

## 解法一：dp

`dp[i]`表示以`s[i]`结尾串的最长有效括号长度，则有两种情况：

1.`s[i] = ')',s[i-1] = '('`，即串形式为`'......()'`:

显然`dp[i] = dp[i-2]+2`

2.`s[i] = ')',s[i-1] = ')'`，即串形式为`'......))'`:

该情况较复杂，找内层`')'`对应的左括号，若存在的话，其位置应该为`i-dp[i-1]-1`，即若`s[i-dp[i-1]-1]=='('`，则dp\[i]等于dp\[i-1]加上`s[i-dp[i-1]-1]`之前的有效括号长度再加上2，即

`dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2`

dp初始全0，一次遍历，得到dp数组，最后求dp中的最大值即可

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = (dp[i-2] if i-2 >= 0 else 0) + 2    #注意下标
                else:    #i-1为右括号
                    if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                        dp[i] = dp[i-1] + (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >=0 else 0) + 2
        return max(dp)
```

## 解法二：栈

一次遍历，栈顶元素为合法括号对`"((...()...))"`的`起点下标-1`，即标记合法括号对的前一位。

初始栈为\[-1]（表示初始假设合法括号对起点为0），遇到左括号就将下标入栈，遇到右括号则弹栈（表示配对一个左括号）。然后判断栈是否为空，若栈空则当前元素入栈，作为新的起点。若非空则计算合法括号对长度，并更新最大值

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        maxLen = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:    #右括号
                stack.pop()
                if len(stack) == 0:    #更新合法括号对起点
                    stack.append(i)
                else:    #否则更新当前括号对长度
                    maxLen = max(maxLen, i-stack[-1])
        return maxLen
```
