给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 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
