最长回文子串

题目描述
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。

解题思路：
暴力穷举法的基础上，改进了回文子串的判断方法，一般的判断一个字串是否回文需要的时间复杂度是O(n)
可以在扫描的过程中记录下某个字串的是否满足回文，为判断其他字串是否是回文提供条件
即如果字串substring(i+1,j-1)是回文，如果string[i]=string[j]，那么substring(i,j)也是回文串。

import java.util.*;

public class Palindrome {

    /**
     * @param String a string
     * @param int the length of the string
     * @return int length of the longest palindrome
     */
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if (n == 0) return 0;
        int max = 1;
        char[] arr = A.toCharArray();
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for (int i = 1; i < n; i ++) {
            dp[i][i] = true;
            dp[i][i-1] = true;
        }
        for (int i = 1; i < n; i ++) {
            for (int j = 0; j < i; j ++) {
                if (dp[j+1][i-1] && arr[i] == arr[j]) {
                    dp[j][i] = true;
                    if (max < i - j + 1) {
                        max = i - j + 1;
                    }
                } else {
                    dp[j][i] = false;
                }
            }
        }
        return max;
    }
}