1. 题目

• 任何一个左括号都能找到和其正确配对的右括号
• 任何一个右括号都能找到和其正确配对的左括号

求最长的有效的括号长度

2. 解释

例如，这里的括号

((((()()()()()()()))()

最长有效是：((()()()()()()()))()

我们来求这个最长。

3. 思路

我们用一个数组来存从当前位置开始，往前N个字符的最长有效字符串。什么意思呢，举个例子：

		( ) ( ) ( ( ) ) (  )  (  )1 2 3 4 5 6 7 8 9 10 11 12
存的数组:0 2 0 4 0 0 2 8 0 10 0  12

3，5等位置为什么为0，3位置是左括号，往前一个是右括号，组不成有效字符串，所以，直接就为0 。

4. 代码

public class Code03_ParenthesesDeep {public static int maxLength(String s){if(s == null || s.equals("")){return 0;}char[] str = s.toCharArray();int[] dp = new int[str.length];int pre = 0;int res = 0;for(int i = 1; i < str.length; i++){if(str[i] == ')'){pre = i - dp[i - 1] - 1;if(pre >= 0 && str[pre] == '('){dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);}}res = Math.max(res, dp[i]);}return res;}public static void main(String[] args) {String s = "(()()";System.out.println(maxLength(s));}
}

运行结果：

4

5. 总结

这里使用了一个动态规划，跟前面的位置进行匹配。