题解 | #最长回文子串#

import java.util.Objects;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }

            //Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，
            // 但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。
            // 因为截获的串太长了，
            // 而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），
            // Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

            // 使用动态规划记录情况 注意动态规划是从内往外扩，也就是i是向右，j是向左
            String res = "";
            boolean[][] dp = new boolean[nextLine.length() + 1][nextLine.length() + 1];
            for (int i = 0; i < nextLine.length(); i++) {
                for (int j = i; j >= 0; j--) {
                    // 前提是首尾一样，并且上一次是回文,如果截取长度小于3 就不用看上一次了，因为它就是首次
                    char end = nextLine.charAt(i);
                    char begin = nextLine.charAt(j);
                    dp[i][j] = end == begin && (i - j < 3 || dp[i - 1][j + 1]);
                    if (dp[i][j] && (i + 1 - j) > res.length()) {
                        res = nextLine.substring(j, i + 1);
                    }
                }
            }
            System.out.println(res.length());

        }
    }
}