最长有效括号 Python

在Python中，最长有效括号问题是经典的动态规划问题，目标是给定一个只包含'('和')'的字符串，找到其中最有效的括号对，使得它们可以按照正确的顺序配对，即形成最大的有效括号序列。这个问题可以用栈来解决。

以下是解决该问题的一种常见算法步骤：

1. 初始化两个变量，`max_len`记录当前找到的有效括号最大长度，`res`记录整个字符串中最长的有效括号长度。

2. 遍历输入的字符串，对于每个字符：
- 如果是'('，将它压入栈中。
- 如果是')'：
- 如果栈不为空且栈顶元素是'('，则匹配一对括号，并更新`max_len`和`res`。
- 否则，不匹配当前')'，跳过剩余的括号，继续检查下一个。

3. 遍历结束后，`res`就是最长有效括号的长度。

下面是简单的Python代码示例：

def longestValidParentheses(s):
    stack = [-1]
    max_len = 0
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack or stack[-1] < stack[-2]:  # 当前右括号无法与栈顶左括号配对
                continue
            max_len = max(max_len, i - stack[-1])  # 更新最长有效括号长度

    return max_len

# 测试样例
s = "(()"
print(longestValidParentheses(s))  # 输出：2，因为有效括号对是 "()"