题解 | #明明的随机数#

• 思路写在注释里

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println(getPalindromeString(new BufferedReader(new InputStreamReader(System.in)).readLine()));
    }

    /**
     * 获取最长回文子串长度
     * @param str
     * @return 最长回文子串长度
     */
    public static int getPalindromeString(String str) {
        char[] chararr = str.toCharArray();
        int len = chararr.length;
        if (chararr.length < 2) return chararr.length;
        int maxLen = 0;
        boolean[][] dp = new boolean[chararr.length][chararr.length];
        /**
         * 从后向前遍历
         */
        for (int i = chararr.length - 1; i >= 0; i--) {
            /**
             * 从当前遍历到的位置向后遍历
             */
            for (int j = i; j < chararr.length; j++) {
                /**
                 * 若两个字母相等，有可能成为回文
                 */
                if (chararr[i] == chararr[j]) {
                    /**
                     * 若两者相等且之间有一个以内的字母，则一定为回文
                     */
                    if (j - i < 3) { 
                        dp[i][j] = true;
                    }
                    /**
                     * 若二者相等，但中间差了2个以上的字母，则有可能是回文
                     * 具体看前者当前位置的后一个及后者当前位置的前一个是否为回文，即dp[i + 1][j - 1]
                     * 如：abcva i=0 j=4
                     *    a和a相等，要看bcv是否是回文，而bcv已经计算过了，位置在dp[1][3]
                     */
                    else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    /**
                     * 若是回文，则更新最长子串
                     */
                    if (dp[i][j]) {
                        if (j - i + 1 > maxLen) {
                            maxLen = j - i + 1;
                        }
                    }
                }
            }
        }

        return maxLen;
    }
}