括号匹配的最大长度问题（进阶版）

题目描述
给定一个只包含 '(' 和 ')' 的字符串s，找出最长有效括号子串的长度。有效括号字符串需满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合

解题思路
这是一个经典的区间动态规划问题。我们可以定义dp[i]表示以第i个字符结尾的最长有效括号子串的长度。通过分析相邻括号的关系和前一个有效子串的情况，可以逐步推导出结果。

详细解题步骤

步骤1：定义状态
定义dp[i]表示以第i个字符结尾的最长有效括号子串的长度。如果s[i]是'('，那么dp[i]必然为0，因为有效括号子串必须以')'结尾。

步骤2：初始化
dp[0] = 0，因为单个字符无法形成有效括号对。

步骤3：状态转移分析
对于每个位置i（i ≥ 1）：

1. 如果s[i] == '('，则dp[i] = 0
2. 如果s[i] == ')'，需要分情况讨论：

   • 情况1：s[i-1] == '('
     此时形成"()"这样的有效对，dp[i] = dp[i-2] + 2

   • 情况2：s[i-1] == ')'
     此时需要检查与当前')'匹配的'('前面的字符
     如果i - dp[i-1] - 1 ≥ 0 且 s[i - dp[i-1] - 1] == '('
     那么dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

步骤4：具体推导过程
以字符串"(()())"为例：

初始：dp = [0,0,0,0,0,0]

i=1: s[1]='(' → dp[1]=0
i=2: s[2]=')'，s[1]='(' → dp[2]=dp[0]+2=0+2=2
i=3: s[3]='(' → dp[3]=0
i=4: s[4]=')'，s[3]='(' → dp[4]=dp[2]+2=2+2=4
i=5: s[5]=')'，s[4]=')'
检查：i-dp[4]-1=5-4-1=0，s[0]='('匹配
dp[5]=dp[4]+2+dp[5-dp[4]-2]=4+2+dp[-1]=6+0=6

最终最长有效括号子串长度为6。

步骤5：边界处理
在计算dp[i - dp[i-1] - 2]时，需要确保索引不越界。如果索引为负数，则对应值为0。

步骤6：算法实现

def longestValidParentheses(s):
    if not s:
        return 0
    
    n = len(s)
    dp = [0] * n
    max_len = 0
    
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = (dp[i-2] if i >= 2 else 0) + 2
            else:  # s[i-1] == ')'
                if i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
                    prev = dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0
                    dp[i] = dp[i-1] + 2 + prev
            max_len = max(max_len, dp[i])
    
    return max_len

步骤7：复杂度分析

• 时间复杂度：O(n)，只需要遍历字符串一次
• 空间复杂度：O(n)，用于存储dp数组

这种方法通过动态规划巧妙地解决了最长有效括号子串问题，确保了线性时间复杂度的解决方案。