"""
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


def longestValidParentheses(s: str) -> int:
    if s is None or s in {'', '(', ')'}:
        return 0
    str_length = len(s)
    record = [0 for _ in range(str_length)]
    record[1] = 2 if s[:2] == '()' else 0

    for i in range(2, str_length):
        if s[i] == '(':
            record[i] = 0
        else:
            if s[i - 1] == '(':
                record[i] = 2 + record[i - 2]
            # 千万注意，python的index是可以为负的，会造成很多莫名其妙的bug
            elif i - record[i - 1] - 1 >= 0 and s[i - record[i - 1] - 1] == '(':
                record[i] = 2 + record[i - 1]
                index = i - record[i - 1] - 2
                if index >= 0:
                    record[i] += record[index]

    #         tmp1 = 2 + record[i-2] if s[i-1] == '(' else 0
    #         tmp2 = 2 + record[i-1] if s[i-1-record[i-1]] == '(' else 0
    #         record[i] = max(tmp1, tmp2)

    # for i in range(len(record)):
    #     if record[i] != 0 and i - record[i] >= 0:
    #         record[i] += record[i - record[i]]

    return max(record)


if __name__ == '__main__':
    print(longestValidParentheses("(()))())("))