题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        //定义dp数组，由于回文串结构，一个字符串可以由dp[i+1][j-1]来推dp[i][j]是否是回文串
        //子问题就是往里缩
        int len = A.length();
        boolean dp[][] = new boolean[len][len];
        int max = 1;
        //从dp[i+1][j-1]来推dp[i][j]可以得出，这个需要从左下往右上进行遍历
        for (int i = len - 1; i >= 0; i--) {
            //j要大于等于i [i,j]
            for (int j = i; j < len; j++) {
                if (A.charAt(i) == A.charAt(j)) {
                    if (j - i <= 1) {
                        //a/aa
                        dp[i][j] = true;
                        max = Math.max(j - i + 1, max);
                    } else if (j - i > 1) {
                        if (dp[i + 1][j - 1]) {
                            dp[i][j] = true;
                            max = Math.max(j - i + 1, max);
                        }
                    }
                }
            }
        }
        return max;
    }
}