题解 | #密码截取#

动态规划，最长回文子字符串

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s=sc.nextLine();
            int ans=0;
            boolean[][] dp=new boolean[s.length()][s.length()];
            for(int i=0;i<s.length();i++){
                dp[i][i]=true;
            }
            //dp数组遍历赋值
            for(int i=s.length()-1;i>=0;i--){
                for(int j=s.length()-1;j>=i;j--){
                    //转移方程
                    dp[i][j]=(s.charAt(i)==s.charAt(j))&&(i==j||j==i+1||dp[i+1][j-1]);
                    if(dp[i][j]==true){
                        ans=Math.max(j-i+1,ans);
                    }
                }
            }
            System.out.println(ans);
            
            
            
        }
        
    }
}