leetcode 032. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"

输出: 4
解释: 最长有效括号子串为 "()()"

思路：
从左向右找，只处理)括号，判断起点位置left，如果前1位的dp有值，那么起点就应再减去长度，即left = i - 1 - dp[i - 1]，如果left>=0并且起点left为(时，当前dp长度为dp[i-1]+2；另外，如果left的前一位也有值，表示字符前面还能连起来，所以还要加上前面的长度，即dp[i] += dp[left -1]

class Solution:
    def longestValidParentheses(self, s):
        if not s:
            return 0
        dp = [0 for _ in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == ')':
                # 判断起点位置为前1位，如果前1位的dp有值起点就为再减去长度
                left = i - 1 - dp[i - 1]
                # 如果起点大于等于0，并且起点为(，则长度为前1个长度+2
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i - 1] + 2
                    # 如果起点前1位dp有值，说明要算上前面的长度
                    if left - 1 >= 0:
                        dp[i] += dp[left - 1]
        print(dp)
        res = max(dp)
        return res