解题思路

对于 最长有效括号子串 问题，常见的两种方法是：

1. 动态规划（DP）
2. 栈（Stack）

方法 1：动态规划（DP）

思路

• 定义 dp[i] 表示 以 i 结尾的 最长有效括号子串的长度。

Leetcode 90.最长有效括号-原题链接

题目描述

给定一个只包含 ( 和 ) 的字符串 s，找出最长的有效（格式正确且连续）括号子串的长度。

输入描述

输入包含一个字符串 s（$0 \leq |s| \leq 3 \times 10^4$），仅包含 ( 和 )。

输出描述

输出一行，表示最长的有效括号子串的长度。

样例输入 1

(()

样例输出 1

2

样例输入 2

)()())

样例输出 2

4

样例输入 3

()

样例输出 3

2

提示

• s 只包含 ( 和 )。
• 结果是 s 中最长的有效括号子串的长度。