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

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

---

动态规划yyds

设 dp[s.length()] 中 dp[i] 为 [0, i] 处最长有效括号长度，经分析输入可分为以下几种情况(前后/中间夹杂着 '(' 或 ')' )

1.  "()()...()()"
2. "((...()...))"
3. "()()...((...()...))"

那么我们对于任何一个合法开头(开头为'(' )的括号字符串都有：

    public int longestValidParentheses(String s) {char[] chars = s.toCharArray();if (chars.length < 2) return 0;int result = 0;int[] dp = new int[chars.length];for (int i = 1; i < chars.length; ++ i) {if (chars[i] == 41) {if (chars[i-1] == 40) {// 三目处理 '()..()..()' 的情况dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;} else if (i-dp[i-1] > 0 && chars[i - dp[i-1] - 1] == 40) {// 三目处理 '()(..(..)..)' 的情况dp[i] = dp[i-1] + (i-dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;}if (dp[i] > result) {result = dp[i];}}}return result;}