每天一道算法题5

【动态规划-有效子串长度】
括号有效配对是指：
1） 任何一个左括号都能找到和其正确配对的右括号
2）任何一个右括号都能找到和其正确配对的左括号
返回一个括号字符串中，最长的括号有效子串的长度

第i的位置如果是左括号，则以第i位置结尾的子串有效长度为0，如果是右括号，
则

pre = i - dp[i-1] - 1;
dp[i] = dp[i-1] + 2 + d[pre - 1];

如： ( ) ( ( ) ）
下标： 0 1 2 3 4 5
长度： 0 2 0 0 2 6

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;
}