给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2:
输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”
有效括号的特性，就是长度一定是偶数，并且在任何位置左括号的数量都是大于等于右括号的数量的，如果在任何位置右括号大于左括号的数量，那么说明这个组成的括号是无效的。根据这个特性我们来看下代码
public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; //从前往后右括号大于左括号，left和right都归0 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } //left大于right先不管 if (left == right) { max = Math.max(max, 2 * right); } else if (right > left) { //right大于left重新记 left = right = 0; } } left = right = 0; //从后往前左括号大于右括号，left和right都归0 for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * left); } else if (left > right) { left = right = 0; } } return max; }dp解法
class Solution { public int longestValidParentheses(String s) { int max = 0; s = " " + s; int dp[] = new int[s.length()]; for (int i = 2; i < s.length(); i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = dp[i - 2] + 2; } else if (s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]; } max = Math.max(max, dp[i]); } } return max; } }