5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        int maxStart = 0, maxLen = 1;
        for (int i = n - 2; i > -1; i--) {
            char si = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char sj = s.charAt(j);
                if (si == sj && (dp[i + 1][j - 1] || j - i < 3)) {
                    dp[i][j] = true;
                    int tmpLen = j - i + 1;
                    if (tmpLen > maxLen) {
                        maxLen = tmpLen;
                        maxStart = i;
                    }
                }
            }
        }
        return s.substring(maxStart, maxStart + maxLen);
    }
}