32. 最长有效括号

32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

开始我还在想为啥题目难度是困难。给的示例就离谱，一点都不有利于人理解题意。动态规划题目。代码：

class Solution { public int longestValidParentheses(String s) { int len = s.length(); int[] dp = new int[len+1]; char[] c = s.toCharArray(); for(int i = 1 ; i < len ; i++){ if(c[i]==')'){ int pre = i - 1 - dp[i-1]; if(pre>=0 && c[pre]=='('){ dp[i] = dp[i-1] + 2; if(pre>0){ dp[i] += dp[pre-1]; } } } } return Arrays.stream(dp).max().getAsInt(); } }

参考了一下别人的代码。看看，多简洁。羡慕。

思路是搜索到右括号的时候，就往前匹配左括号，与哪个位置匹配，取决于上一个位置已经匹配的长度。最后还有要处理括号对连在一起的情况。具体看代码吧，不难理解。