平衡括号(五)——最长平衡括号子串

LeetCode_32_LongestValidParentheses

题目分析：

其实这题并没有用上平衡括号特性，只是一个以平衡括号为载体的dp题。
算是个收集癖写在这里。但是记得这跟平衡括号，其实没啥特别关系。
要用上dp了。子串常见的定义法。就是另dp[i]为
"以i为结尾"
"以i为结尾"
"以i为结尾"
的子串的对应结果。
方程
  1.s[i]如果是左括号，一个左括号结尾自然是0。
  2.s[i]如果是右括号
    就看在dp[i - 1]的"对称位置"是否是左括号
    int pre = i - dp[i - 1] - 1;//对称
    2.1如果不是，一个右括号结尾，就是0。
    2.2如果是
    if(pre >= 0 && chas[pre] == '(')
    长度就扩充2。并且！！！如果pre不是开始位置，加上dp[pre - 1]。
    为了这种情况 ()(()) 续上之前的子串。
    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);

解法：

public static int longestValidParentheses2(String s) {
    /**
     * 动态规划，dp[i]为以s[i]为结尾的最长有效字串长度
     * s[i]=='('，dp[i]为零
     * s[i]=')',看对称位置是否为'(',注意()(()),这种情况，前面也得加上
     * 和我想法一样 但是没有写下去 凸(艹皿艹 )
     */
    char[] chas = s.toCharArray();
    int[] dp = new int[chas.length];
    int res = 0;
    for(int i = 1; i < chas.length; i++){
        if(chas[i] == ')'){
            int pre = i - dp[i - 1] - 1;//对称
            if(pre >= 0 && chas[pre] == '('){
                /**
                 * pre > 0 ? dp[pre - 1] : 0
                 * 解决了  ()(())  这种情况的连接问题
                 */
                dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}