括号匹配的最大长度问题（基础版本） 题目描述： 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长有效（格式正确且连续）括号子串的长度。 有效括号字符串需满足： 空字符串是有效的 如果 A 是有效的，则 (A) 也是有效的 如果 A 和 B 是有效的，则 AB 也是有效的 解题过程： 问题分析 我们需要找到最长的连续子串，该子串中的括号是正确匹配的。例如： "(()" 的最长有效括号子串长度为 2（"()"） ")()())" 的最长有效括号子串长度为 4（"()()"） 动态规划定义 定义 dp[ i ] 表示以第 i 个字符结尾的最长有效括号子串的长度。 状态转移分析 情况1：当 s[ i] = ')' 且 s[ i-1 ] = '(' 时 形如 "...()"，那么 dp[ i] = dp[ i-2 ] + 2 情况2：当 s[ i] = ')' 且 s[ i-1 ] = ')' 时 形如 "...))"，需要检查 s[ i - dp[ i-1] - 1 ] 是否为 '(' 如果是，那么 dp[ i] = dp[ i-1] + 2 + dp[ i - dp[ i-1] - 2 ] 边界条件 如果 i < 1，dp[ i ] = 0 如果遇到无法匹配的情况，dp[ i ] = 0 算法步骤 (1) 初始化 dp 数组全为 0 (2) 遍历字符串的每个位置 i（从索引 1 开始） (3) 如果 s[ i ] = ')'： 如果 s[ i-1] = '('：dp[ i] = (i >= 2 ? dp[ i-2 ] : 0) + 2 如果 s[ i-1] = ')' 且 i-dp[ i-1]-1 >= 0 且 s[ i-dp[ i-1]-1 ] == '('： dp[ i] = dp[ i-1] + 2 + (i-dp[ i-1]-2 >= 0 ? dp[ i-dp[ i-1]-2 ] : 0) (4) 记录最大的 dp[ i ] 值 示例演示 以 s = "()(())" 为例： 索引: 0 1 2 3 4 5 字符: ( ) ( ( ) ) dp值: 0 2 0 0 2 6 计算过程： i=1: "()" → dp[ 1] = dp[ -1 ] + 2 = 0 + 2 = 2 i=4: "(())" 的内层 → dp[ 4] = dp[ 3] + 2 + dp[ 2 ] = 0 + 2 + 0 = 2 i=5: 完整匹配 → dp[ 5] = dp[ 4] + 2 + dp[ 1 ] = 2 + 2 + 2 = 6 最终最长有效括号子串长度为 6。