题目描述

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

示例1

输入
"abc1234321ab",12
返回值
7

思路

1.转移方程容易想，但两个指针的移动方向容易出错。
2.应该A指针向右走，B指针从A开始向左走，目的是B指针扫过的范围A已经走过，才能执行动态规划。

code

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        boolean [][]dp = new boolean[n+1][n+1];
        for(int i=0;i<n;i++)dp[i][i]=true;
        char []chs = A.toCharArray();
        int max = 0;
        for(int i=0;i<n;i++){
            for(int j=i;j>=0;j--){
                if(j+1==i){
                    dp[j][i] = chs[j]==chs[i];
                    if(i-j+1>max)max=i-j+1;
                }else if(j+1<i){
                    if(dp[j+1][i-1]==true && chs[j]==chs[i]){
                        dp[j][i] = true;
                        if(i-j+1>max)max=i-j+1;
                    }
                    else dp[j][i]=false;
                }
            }
        }
        return max;
    }
}