'''
性质1：有效括号两个条件
（1）每个点的左括号数量大于等于右括号数量
（2）最终点左括号数量等于右括号数量
性质2：分界点
构造辅助数组，如果对于')'能找到对应的'('，则两者都标记为1，否则为0
")()())" 的有效匹配是011110，易知有效匹配不能跨越0
所以就是查找最长的连续1的数量
性质3：
括号序列左右翻转还是括号序列，具有对称性

思路1:成对匹配
构造辅助数组，如果对于')'能找到对应的'('，则两者都标记为1，否则为0。查找辅助数组连续1的数量
    方式1：
    不用辅助数组，通过栈模拟寻找成对括号，栈中只存储'('。
    连续1的数量就是当前')'减去对应的'('的前一个无效匹配字符的下标
    方式2：
    对辅助数组进行遍历，查找最长连续1的数量
思路2：前缀和与后缀和
i = -1 # 初始分界点
i、j代表当前分段范围，f[j]代表s[i:j]中'('数量前缀和与')'数量前缀和的差值。如果f[j]<0, 新的分界点i = j
求每个分界段长度的最大值
如果最后一个分界段如同'(((((((()',则输出错误结果
由于括号序列的对称性，
改进如下：求字符串括号后缀和之差得到g[j], 当f[j]=0或g[j]=0时，才计算当前分界段的长度
比如'()))((()'就能得到f = [1, 0, -1, -1, 1, 2, 3, 2], g = [2, 3, 2, 1, -1, -1, 0, 1]
注意：
分界点start的起始位置
处理f[i]、g[i]的位置
思路3：动态规划
f[i]以字符s[i]为结尾的括号序列的最大长度
初始化：f[0] = 0
if s[i] == '(': # 无法成对
    f[i] = 0
else: # 只对')'计算f[i]
    if s[i-1]=='(': # 不在乎f[i-2]是哪种括号
        f[i] = f[i-2] + 2
    else: # 找对应的'('位置, 在i - 1 - f[i-1]处
        # 如果f[i - 1 - f[i-1]]不存在或不是'(', 则代表失配
        # 不在乎f[i - 2 - f[i-1]]是哪种括号
        f[i] = f[i-1] + f[i - 2 - f[i-1]] + 2
'''
###思路1方式1###
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        stk = list() #用来匹配'('和')'
        start = -1
        res = 0 #最大距离
        for i in range(n):
            if s[i] == '(':
                stk.append(i)
            else:
                if not stk: # 找不到对应'('
                    start = i
                else:
                    stk.pop()
                    if stk:
                        res = max(res, i - stk[-1]) #避免多余的'('
                    else:
                        res = max(res, i - start)
        return res

###思路2###
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        f, g = [[0 for i in range(n)] for j in range(2)]
        res = 0
        # f[i]代表'('前缀和 减 ')'前缀和
        f[0] = 1 if s[0] == '(' else -1
        start = -1 if f[0] == 1 else 0 # 分段起点，值为-1对应的下标
        for i in range(1, n):
            # 计算f[i]
            if f[i-1] >= 0:
                if s[i] == '(':
                    f[i] = f[i-1] + 1
                else:
                    f[i] = f[i-1] - 1
            else:
                f[i] = 1 if s[i] == '(' else -1
            # 处理f[i]
            if f[i] == 0: # 只有f[i]为0时，才统计该分段的长度
                res = max(res, i - start)
            if f[i] < 0:
                start = i # 更新分段
        # g[i]代表')'后缀和 减 '('后缀和
        g[n-1] = 1 if s[n-1] == ')' else -1
        start = n if g[n-1] == 1 else n - 1
        for i in range(n-2, -1, -1):
            # 计算g[i]
            if g[i+1] >= 0:
                if s[i] == ')':
                    g[i] = g[i+1] + 1
                else:
                    g[i] = g[i+1] - 1
            else:
                g[i] = 1 if s[i] == ')' else -1
            # 处理g[i]
            if g[i] == 0: # 只有g[i]为0时，才统计该分段的长度
                print(start, i)
                res = max(res, start - i)
            if g[i] < 0:
                start = i # 更新分段
        return res
###思路3###
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        f = [0 for i in range(n)]
        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    if i >= 2:
                        f[i] = f[i-2] + 2
                    else:
                        f[i] = 2
                else:
                    idx = i - 1 - f[i - 1] # '('所在位置
                    if idx >= 0 and s[idx] == '(':
                        if idx >= 1: 
                            f[i] = f[i-1] + f[idx-1] + 2
                        else: 
                            f[i] = f[i-1] + 2
        return max(f)