题解 | #最长的括号子串#

动态规划：
g[i]表示以s[i]结尾的最长合法字符串的长度；令d[i]为以s[i]结尾的最长合法字符串的首下标，d[i]=i+1-g[i]；使用变量maxlen跟踪最长字符串长度。
已知g[i-1]，计算g[i]：

1. 若s[i]=='('，则g[i]==0;
2. 若s[i]==')’，检查下标为d[i-1]-1=i-1-g[i-1]是否为'('。若是，则:
   g[i]=g[i-1]+2
   再检查该合法字符串是否与上一个合法字符串相连，即检查下标为d[i]-1=i-g[i]存在最长合法字符串，即检查g[i-g[i]]>0。若是，则两个字符长度相加:
   g[i] = g[i] + g[i-g[i]]
   

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