题解 | #密码截取#动态归划

import java.util.Scanner;

// 如果最大回文子串的长度等于字符串长度，则说明是回文字符串
// 一个回文串的两端相同，去掉两端后还是回文串
// 采用动归的方式不段求最大回文子串长度
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int len = input.length();
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) { // 横向遍历
            dp[i][i] = 1; // 单个字符串就是回文字符串
            for (int j = i + 1; j < len; j++) { // 非单个字符的判断，纵向遍历
                if (input.charAt(i) == input.charAt(
                            j)) { // 两边字符相同，判断内部是否是回文串
                    if (j - i - 1 == dp[i + 1][j -
                                               1]) { // 如果是回文串，则最大回文子串长度等于字符串长度
                        dp[i][j] = dp[i + 1][j - 1] + 2; // 回文串长度加2
                        continue;
                    }
                }
                // 不是回文串，则最长回文子串的长度在内部
                dp[i][j] = Math.max(
                               dp[i + 1][j], // 左边的一个
                               dp[i][j - 1] // 右边的一个
                           );
            }
        }
        System.out.println(dp[0][len - 1]);
    }
}