给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
首先想到用栈做字符匹配 原本思路是push入‘（ ’ 后如果下一个是‘ ）’ 则让子数组长度加2 发现中间有无法匹配的括号符的时候不好处理 如“( ( ) ( ( )”采用这个思路会输出4 而正确长度应该是2，因为两个“（）”中间还有个“（ ”。 换个思路： 把字符串的字符对应的下标push入栈 i - (int)stack.peek()就是子字符串的长度。
public static int longestValidParentheses(String s) { if(s == "")return 0; int len = 0; Stack stack = new Stack(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.empty()) { stack.push(i); } else { len = Math.max(len, i - (int)stack.peek()); } } } return len; }可惜速度一般 还有一个方法是动态规划 每次判断两个符号 i 和 i-1 如果两个是“(” ")"的形式 就直接让dp[ i ] = （d[i-1]或者0） + 2; i-1>=0则是d[i-1]，反之是0. 如果两个是“）” ” ）“的形式，就看之前的i-dp[i-1]-1的位置上是不是“（” 是的话说明可以匹配到，则让 dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2]或0) + 2;
class Solution { public int longestValidParentheses(String s) { if(s=="") return 0; int[] dp = new int[s.length()]; int len = 0; for(int i = 1;i < dp.length;i ++) { if(s.charAt(i)==')'){ if(s.charAt(i-1)=='(') { dp[i]+=2+(i-2>=0? dp[i-2] : 0); len = Math.max(len, dp[i]); } else if(s.charAt(i-1)==')'&&i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='(') { dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; len = Math.max(len, dp[i]); } } } return len; } }