Q:求一个字符串的最长回文子串
A:经典问题

public class 最长回文子串 
{
    //第一步先决策出最长的子串的长度
    public static boolean[][] first(char[] arr)
    {
        boolean[][] dp=new boolean[arr.length][arr.length];
        for (int i=0;i<arr.length-1 ;i++ )
        {
            dp[i][i]=true;
            if (arr[i]==arr[i+1])
            {
                dp[i][i+1]=true;
            }
        }
        dp[arr.length-1][arr.length-1]=true;
        for (int len=3;len<=arr.length ;len++ )
        {
            for (int i=0;i<=arr.length-len ;i++ )
            {
                //i=arr.length-len时，j刚好为arr.length-1
                int j=i+len-1;
                if (arr[i]==arr[j]&&dp[i+1][j-1])
                {
                    dp[i][j]=true;
                }
            }
        }
        return dp;
    }
    //第二步从第一步的决策，还原出最长的子串
    public static String second(char[] arr,boolean[][] dp)
    {
        String str=null;
        int len=arr.length-1;
        int i=0;
        outer:
        while (len>0)
        {
            i=0;
            for (int j=i+len;j<=arr.length-1 ;i++,j++ )
            {
                if (dp[i][j])
                {
                    str= new String(arr,i,j-i+1);
                    break outer;
                }
            }
            len--;
        }
        return str;
    }
    public static void main(String[] args) 
    {
        String str="AABACD";
        char[] arr=str.toCharArray();
        boolean[][] dp=first(arr);
        System.out.println(second(arr,dp));
    }
}