/**
*
* 问题：括号字符串的最长有效长度
* 给定一个括号字符串返回最长的有效字符串子串
*
* 分析：
* 用动态规划求解，可以做到时间复杂度为O(N), 额外空间复杂度为O(N)。
* 首先生成长度和str字符串一样的数组dp[],dp[i]值的含义为str[O .. i]中必须以字符str[i]结
* 尾的最长的有效括号子串长度。那么dp[i]值可以按如下方式求解：
* 1. dp[O]=O。只含有一个字符肯定不是有效括号字符串， 长度自然是0。
* 2. 从左到右依次遍历str[I .. N-1]的每个字符， 假设遍历到str[i].
* 3. 如果str[i]="(", 有效括号字符串必然是以")"结尾， 而不是以"("结尾，所以dp[i]= 0。
* 4. 如果str[i]=")", 那么以str[i]结尾的最长有效括号子串可能存在。dp[i-1]的值代表必
* 须以str[i-1]结尾的最长有效括号子串的长度，所以如果i-dp[i-1]-1位置上的字符是"("，
* 就能与当前位置的str[i]字符再配出一对有效括号。比如"(()())", 假设遍历到最后一个
* 字符")"，必须以倒数第二个字符结尾的最长有效括号子串是"()()",找到这个子串之前的字
* 符，即i-dp[i-1]-1位置的字符，发现是"(" ,所以它可以和最后一个字符再配出一对有效括
* 号。如果该情况发生， dp[i]的值起码是dp[i-1]+2, 但还有一部分长度容易被人忽略。比
* 如"()(())",假设遍历到最后一个字符")"，通过上面的过程找到的必须以最后字符结尾的最
* 长有效括号子串起码是"(())",但是前面还有一段"()"可以和"(())"结合在一起构成更大的
* 有效括号子串。也就是说，str[i-dp[i-1]- 2]和str[i]配成了一对，这时还应该把
* dp[i-dp[i-1]-2]的值加到dp[i]中，这么做表示把str[i-dp[i-1]-2]结尾的最长有效括号子
* 串接到前面， 才能得到以当前字符结尾的最长有效括号子串。
* 5. dp[ .. N-1]中的最大值就是最终的结果。
*
* @author 雪瞳
* @Slogan 时钟尚且前行，人怎能再此止步！
* @Function
*
*/
public class MaxLength {
public static int maxLength(String string){
if (string == null || "".equals(string)){
return 0;
}
char[] chars = string.toCharArray();
int[] dp = new int[chars.length];
int pre = 0;
int res = 0;
for (int i=1;i<chars.length;i++){
if (")".equals(chars[i])){
pre = i - dp[i-1] -1;
if (pre >=0 && "(".equals(chars[pre])){
dp[i] = dp[i-1]+2+(pre>0?dp[pre-1]:0);
}
}
res = Math.max(res,dp[i]);
}
return res;
}
}