问题背景

最长回文子串指的是一个字符串中的连续字符序列，该序列从前往后读和从后往前读是一样的。例如，字符串 "abcbad" 的最长回文子串是 "abcba"。

本文将介绍使用 Java 语言解决这个问题的方法。其中，我们将使用动态规划算法，该算法在解决最长回文子串问题时具有较好的时间复杂度。

动态规划算法

动态规划算法的基本思想是将一个复杂问题分解为若干个子问题，并通过记录和利用已解决的子问题的结果来求解整个问题。

在求解最长回文子串的问题中，我们可以使用一个二维数组 dp[i][j] 来表示子串 s[i...j] 是否为回文串。其中，dp[i][j] 的值为 true 表示 s[i...j] 是一个回文串，否则为 false。

求解过程

1. 初始化 dp 数组，将对角线上的元素和相邻元素（长度为 1 和 2 的子串）设为 true。

2. 根据子串长度递增的顺序，遍历所有可能的子串长度，更新 dp 数组。对于长度大于 2 的子串 s[i...j]，如果 s[i] 和 s[j] 相等，并且 s[i+1...j-1] 也是回文串，则 s[i...j] 也是回文串（即 dp[i][j]=true），否则不是。

3. 在更新 dp 数组的过程中，记录最长的回文子串的长度和起始位置，即维护两个变量 start 和 maxLength。若 dp[i][j] 为 true 且 j-i+1 大于 maxLength，则更新 start 和 maxLength 的值。

4. 根据得到的最长回文子串的起始位置和长度，即可得到最长回文子串。

public static String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0;
    int maxLength = 1;
    
    // 初始化dp数组
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    
    // 更新dp数组
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLength) {
                    start = i;
                    maxLength = len;
                }
            }
        }
    }
    
    // 获取最长回文子串
    return s.substring(start, start + maxLength);
}
Java