给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"思路：看到括号匹配第一想法就是栈模拟，但是他求的是连续的子串，很容易就想到动态规划，思路见注释
public int longestValidParentheses(String s) { int res = 0; if(s.length() <= 1) { return res; } //dp[i]表示以i位结尾的最长子串长度 int[] dp = new int[s.length()]; dp[1] = s.charAt(0)=='('&&s.charAt(1)==')'?2:0; res = dp[1]; for (int i = 2; i < s.length(); i++) { //以')'结尾要看前一个字符，可分为两种情况 if(s.charAt(i) == ')'){ if(s.charAt(i-1) == ')'){ //比如"()(())" if(i-1-dp[i-1] >= 0&& s.charAt(i-1-dp[i-1])=='('){ dp[i] = dp[i-1]+2+(i-2-dp[i-1] >= 0 ?dp[i-2-dp[i-1]]:0); } res = Math.max(dp[i], res); }else { //比如"()()" dp[i] = dp[i-2]+2; res = Math.max(dp[i] , res); } } //以'('结尾必然不可能和前面的子串连续，即长度为0 } return res; }