题解 | #最长的括号子串#

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        if (s == null || s.length() < 2) {
            return 0;
        }

        int len = s.length();

        int[] dp = new int[len]; // 存储到此下标及包括下标字符在内的最大括号子串长度
        char[] ss = s.toCharArray();

        int res = 0;

        for (int i = 1; i < len; i++) {
            if (ss[i] == ')') {
                int pre = i - dp[i - 1] - 1;
                if (pre >= 0 && ss[pre] == '(') {
                    dp[i] = dp[i - 1] + 2; // 如果匹配上就+2
                    if (pre - 1 >= 0) {
                        dp[i] += dp[pre - 1]; // 还能把相邻的最长子串一起纳入，这就是dp维护到此下标包含下标最长子串的好处
                    }

                    res = Math.max(res, dp[i]); // 更新最大值
                }
            }
        }

        return res;
    }
}