最长的括号子串

class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        n = len(s)
        if (n == 0&nbs***bsp;n == 1):
            return 0
        
        # num[i]表示以s[i]结尾的最大正确括号长度
        # 我们使用动态规划求出num，然后返回max(num)
        # 时间和空间复杂度均为O(n)
        num = [0 for i in range(n)]
        
        for i in range(1, n):
            
            #如果结尾是左括号，那必定是没有以左括号结尾的正确子串的
            if (s[i] == '('):
                num[i] = 0
            
            # 如果是右括号结尾
            else:
                # 记以s[i-1]结尾的最长子串长度为k
                # 即s[i-k: i]为前面的正确括号子串，我们要对比i和i-k-1是否能在外面继续形成一对括号
                k = num[i-1]
                # 首先判断i-k-1是否存在
                if (i-k-1 < 0):
                    
                    # 若前面没有i-k-1了,意味着i==k，也就是前i个字符有i和正确括号，刚好匹配完
                    # 那么s[i]只可能与s[i-1]形成括号对
                    if (s[i-1] == '('):
                        num[i] = 2
                    else:
                        num[i] = 0
                    continue
                
                # 如果前面的i-k-1>=0
                if (s[i] == ')' and s[i-k-1] == '('):
                    # 这里s[i]和s[i-k-1]在s[i-k :i]外面又构成了一对括号，因此长度加二
                    num[i] = num[i-1] + 2
                    # 这里我们要判断长度加二的新括号串s[i-k-1,i-1]会不会跟s[i-k-2]为结尾的括号串连起来
                    if (i-k-2 >=1):
                        num[i] += num[i-k-2]
                
        print(num)                
        return max(num)
        

class Solution:
    def longestValidParentheses(self , s ):
        # write code here
        n = len(s)
        g = [0]*n
        maxlen = 0
        for i in range(1, n):
            if s[i]==')' and i-1-g[i-1]>=0 and s[i-1-g[i-1]]=='(':
                g[i] = g[i-1] + 2
                if i-g[i]>=0 and g[i-g[i]]>0:
                    g[i] += g[i-g[i]]
                maxlen= max(maxlen, g[i])
        return maxlen