解法1：暴力解法

直接判断每一个子串是不是回文子串，然后取其中最长的值返回

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        int maxLen = 0;
        //暴力解法
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                String now = A.substring(i,j);
                if(isPalindrome(now) && now.length() > maxLen){
                    maxLen = now.length();
                }
            }
        }
        return maxLen;
    }

    //判断子串是不是回文子串
    public boolean isPalindrome(String s){
        int l = s.length();
        for(int i = 0; i < l/2; i++){
            if(s.charAt(i) != s.charAt(l-i-1))
                return false;
        }
        return true;
    }
}

解法2：动态规划

动态规划算法中两个重要概念是边界以及状态转移方程；
dp[i][j]是一个bool类型的变量数组，如果dp[i][j]==true,那么他表示字符串str从str[i]到str[j]是回文串

  • 边界是：dp[i][i]=true,dp[i][i+1]=(str[i]==str[i+1]) ? true , false

状态转移方程：

  • dp[i][j]=true if( dp[i+1][j-1] && str[i]==str[j] )

  • dp[i][j]=false if( str[i]!=str[j] )

    public int getLongestPalindrome(String A, int n) {
      // write code here
      boolean[][] dp = new boolean[n][n];
      String ans = "";
      //l:字符串首尾字母长度差 (d = j-i)
      for (int l = 0; l < n; ++l){// 字符串起始位置 i
          for (int i = 0; i + l < n; ++i) {
              int j = i + l;// 字符串结束位置 j
              if (l == 0) {
                  dp[i][j] = true;
              } else if (l == 1) {
                  dp[i][j] = (A.charAt(i) == A.charAt(j));
              } else {
                  dp[i][j] = (A.charAt(i) == A.charAt(j) && dp[i + 1][j - 1]);
              }
              if (dp[i][j] && l + 1 > ans.length()) {
                  // 更新最大长度
                  ans = A.substring(i, i + l + 1);
              }
          }
      }
      return ans.length();
  }

    解法3：中心扩散法

    https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
    中心扩散法怎么去找回文串？
    从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str=acdbbdaa 我们需要寻找从第一个 b（位置为 33）出发最长回文串为多少。怎么寻找？
    首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
    然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
    最后左右双向扩散，直到左和右不相等。如下图所示：
    图片说明
    每个位置向两边扩散都会出现一个窗口大小（len）;
    如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。
    因为我们最后要返回的是具体子串，而不是长度，
    因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=len。
    时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。

    public class Palindrome {
  public int getLongestPalindrome(String A, int n) {
      if(n == 0)
          return 0;
      int maxLen = 1;
      //中心枚举到n-2位置
      for(int i = 0; i < n-1; i++){
          // 比较以i为中心扩散的回文子串 
          //&& 以i和i+1为中心扩散的回文子串 哪个大取哪个
          int len = centerSpread(A,i,i) > centerSpread(A,i,i+1)? centerSpread(A,i,i):centerSpread(A,i,i+1);
          maxLen = Math.max(maxLen,len);   
      }
      return maxLen;
  }

  //若left==right 则扩散中点为一个，此时的回文子串为奇数
  //若left!=right，则扩散的中点为 left和right，此时的回文子串为偶数
  public int centerSpread(String s, int left, int right){
      int len = s.length();
      int l = left;
      int r = right;
      while(l >= 0 && r <= len-1){
          //若相等则继续扩散
          if(s.charAt(l) == s.charAt(r)){
              l--;
              r++;
          }else{
              break;
          }
      }
      //为什么还要减2  因为上面while循环终止了，此时s.charAt(l) != s.charAt(r)
      //所以此时的回文子串的左右边界其实是  l-1，  r-1
      return r-l+1-2;
  }
}