经典问题，直接贴代码

public class 最长回文子序列 
{
    //第一步先决策出长度
    public static int[][] first(char[] arr)
    {
        int[][] dp=new int[arr.length][arr.length];
        for (int i=0;i<arr.length-1 ;i++ )
        {
            dp[i][i]=1;
            if (arr[i]==arr[i+1])
            {
                dp[i][i+1]=2;
            }
            else
                dp[i][i+1]=1;
        }
        dp[arr.length-1][arr.length-1]=1;
        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][j]=dp[i+1][j-1]+2;
                }
                else
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp;
    }
    //第二步根据决策信息得到最长回文子序列
    public static String second(char[] arr,int[][] dp)
    {
        StringBuilder sb=new StringBuilder();
        int index=0;
        int row=0;
        int col=arr.length-1;
        while (row<=col)
        {
            int i=row;
            int j=col;
            if (dp[i][j]==dp[i][j-1])
            {
                col--;
            }
            else if (dp[i][j]==dp[i+1][j])
            {
                row++;
            }
            else
            {
                row++;
                col--;
                sb.insert(index,arr[i]+"");
                index++;
                if (i!=j)
                {
                    sb.insert(index,arr[j]+"");
                }
            }
        }
        return sb.toString();
    }
    public static void main(String[] args) 
    {
        String str="ABCDACB";
        char[] arr=str.toCharArray();
        int[][] dp=first(arr);
        System.out.println(second(arr,dp));
    }
}