题解 | #密码截取#动态归划
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
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]);
}
}
#最长回文子串#