給定一個只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號的子串的長度。

示例 1:

輸入: "(()"
輸出: 2
解釋: 最長有效括號子串為 "()"

示例 2:

輸入: ")()())"

輸出: 4
解釋: 最長有效括號子串為 "()()"

思路：
從左向右找，只處理)括號，判斷起點(diǎn)位置left，如果前1位的dp有值，那么起點(diǎn)就應(yīng)再減去長度，即left = i - 1 - dp[i - 1]，如果left>=0并且起點(diǎn)left為(時，當(dāng)前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] == ')':
                # 判斷起點(diǎn)位置為前1位，如果前1位的dp有值起點(diǎn)就為再減去長度
                left = i - 1 - dp[i - 1]
                # 如果起點(diǎn)大于等于0，并且起點(diǎn)為(，則長度為前1個長度+2
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i - 1] + 2
                    # 如果起點(diǎn)前1位dp有值，說明要算上前面的長度
                    if left - 1 >= 0:
                        dp[i] += dp[left - 1]
        print(dp)
        res = max(dp)
        return res