题解 | #密码截取#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        int[][] maxLen = new int[line.length()][line.length()];

        for (int i = 0; i < line.length(); i++) {
            maxLen[i][i] = 1;
            if (i > 0 && line.charAt(i) == line.charAt(i - 1)) {
                maxLen[i-1][i] = 2;
            }
            else if (i > 0 && line.charAt(i) != line.charAt(i - 1)) {
                maxLen[i-1][i] = 1;
            }
        }

        for (int i = 2; i < line.length(); i++) {
            for (int j = 0; j + i < line.length(); j++) {
                if (line.charAt(j) == line.charAt(j + i) && maxLen[j + 1][j + i - 1] == i - 1) {
                    maxLen[j][j+i] = i + 1;
                }
                else {
                    if (maxLen[j][j+i-1] > maxLen[j+1][j+i]) {
                        maxLen[j][j+i] = maxLen[j][j+i-1];
                    }
                    else {
                        maxLen[j][j+i] = maxLen[j+1][j+i];
                    }
                }
            }
        }
        System.out.println(maxLen[0][line.length() - 1]);
    }
}

maxLen[i][j]为str[i,j]内部最长对称字串

若c[i]==c[j], 且str[i+1, j-1]为对称字串，则str[i,j]也为对称字串

若c[i]!=c[j],则maxLen[i][j] = max{ maxLen[i+1][j], maxLen[i][j-1] }