括号匹配的最大长度问题（进阶版） 题目描述： 给定一个只包含 '(' 和 ')' 的字符串，找到最长的有效（格式正确且连续）括号子串的长度。 解题过程： 步骤1：理解问题 有效括号字符串需要满足： 每个左括号 '(' 都有对应的右括号 ')' 左括号必须在对应的右括号之前 括号必须正确嵌套 步骤2：定义状态 令 dp[ i ] 表示以第 i 个字符结尾的最长有效括号子串的长度 我们只考虑以 ')' 结尾的情况，因为以 '(' 结尾的肯定不是有效括号串 步骤3：状态转移方程分析 情况1：当前字符是 ')'，前一个字符是 '(' 形如 "...()"，那么： dp[ i] = dp[ i-2 ] + 2 （如果 i >= 2） 或者 dp[ i] = 2 （如果 i < 2） 情况2：当前字符是 ')'，前一个字符也是 ')' 形如 "...))"，我们需要检查与当前 ')' 匹配的 '(' 是否存在 如果 s[ i-dp[ i-1]-1 ] == '('，那么： dp[ i] = dp[ i-1] + 2 + dp[ i-dp[ i-1]-2 ] 解释： dp[ i-1 ] 是以 i-1 结尾的有效长度 i-dp[ i-1 ]-1 是可能与当前 ')' 匹配的左括号位置 如果匹配成功，当前有效长度 = 内部有效长度 + 2 + 前面的有效长度 步骤4：边界条件 如果字符串长度小于2，直接返回0 dp[ 0 ] = 0（单个字符不可能是有效括号） 步骤5：算法实现思路 创建dp数组，长度与字符串相同，初始化为0 从索引1开始遍历字符串 如果当前字符是 ')'： 如果前一个字符是 '('，按情况1处理 如果前一个字符是 ')'，按情况2处理 在遍历过程中记录最大的dp值 步骤6：示例演示 以字符串 "()(())" 为例： 索引: 0 1 2 3 4 5 字符: ( ) ( ( ) ) dp: 0 2 0 0 2 6 计算过程： i=1: "()" → dp[ 1 ] = 2 i=2: "(" → dp[ 2 ] = 0 i=3: "(" → dp[ 3 ] = 0 i=4: "())" → 检查 s[ 3]='('，匹配成功 → dp[ 4 ] = 2 i=5: "())" → 检查 s[ 2]='('，匹配成功 → dp[ 5] = dp[ 4] + 2 + dp[ 1 ] = 2 + 2 + 2 = 6 步骤7：复杂度分析 时间复杂度：O(n)，只需要遍历一次字符串 空间复杂度：O(n)，用于dp数组存储 这个解法通过动态规划巧妙地记录了以每个位置结尾的最长有效括号长度，最终取最大值即为答案。