32. 最长有效括号

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中的最大值即可

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），遇到左括号就将下标入栈，遇到右括号则弹栈（表示配对一个左括号）。然后判断栈是否为空，若栈空则当前元素入栈，作为新的起点。若非空则计算合法括号对长度，并更新最大值

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