公共子序列与公共子串不同在于子序列不要求连续。利用两个二维数组进行求解，c数组负责存值，求得子序列最大长度，即途中0123。b数组进行符号标记，通过b数组还原访问顺序，即图中箭头，通过它得到完整子序列。

字符串35328与2579312比较

public static void LCS(int[][] b,int[][] c,String str1, String str2) {  
        int m=str1.length();
        int n=str2.length();
        char[] x=str1.toCharArray();
        char[] y=str2.toCharArray();
//        for(int i=0;i<=m;i++)
//          c[i][0]=0;
//        for(int j=0;j<=n;j++)
//          c[0][j]=0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(x[i-1]==y[j-1]){
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else if(c[i-1][j]>=c[i][j-1]){
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                }
                else {
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
    }  

输出最长公共子序列

public static void printLCS(int[][] b,String x,int i,int j){
        if(i==0||j==0){
            return;
        }
        if(b[i][j]==1){
            printLCS(b,x,i-1,j-1);
            System.out.print(x.charAt(i-1));//x的值比二维矩阵的x值少1,画图更容易理解
        }
        else if(b[i][j]==2)
            printLCS(b,x,i-1,j);
        else printLCS(b,x,i,j-1);
    }

主程序 二维数组声明时长度时字符串长度+1，因为下标计数从0开始所以调用输出函数时参数为字符串长度。

 public static void main(String[] args){
        String s1="35328";String s2="2579312";
        int[][] b=new int[s1.length()+1][s2.length()+1];
        int[][] c=new int[s1.length()+1][s2.length()+1];
        LCS(b,c,s1,s2);
        printLCS(b,s1,s1.length(),s2.length());
    }

为了方便理解 贴出算法导论中伪代码帮助理解：

伪代码,建立b,c二维数组 伪代码，输出最长公共子序列

优化: 不使用b数组存储方向

算法导论中提出问题 能否不通过数组b存储方向而得到最长公共子序列呢？答案是可以。即通过对数组c[i][j]与其上方左方数组的比较得到。c[i][j] = ( c[i-1][j] >= c[i][j-1] ? c[i-1][j] : c[i][j-1]); 代码如下

public static int[][] LCS(String str1, String str2) {  
        int[][] c=new int[str1.length()+1][str2.length()+1];    
        int m=str1.length();
            int n=str2.length();
            char[] x=str1.toCharArray();
            char[] y=str2.toCharArray();
            for(int i=0;i<=m;i++)
                c[i][0]=0;
            for(int j=0;j<=n;j++)
                c[0][j]=0;
            for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++){
                    if(x[i-1]==y[j-1]){
                        c[i][j]=c[i-1][j-1]+1;
                    }
                    else {
                        c[i][j] = ( c[i-1][j] >= c[i][j-1] ? c[i-1][j] : c[i][j-1]); 
                    }
                }
        return c;
    }  

    public static void print(int[][] b, String X, String Y, int i, int j) {  
      
        if (i == 0 || j == 0) {  
            return;  
        }  
          
        if (X.charAt(i - 1) == Y.charAt(j - 1)) {  
                print(b, X, Y, i - 1, j - 1);  
                System.out.print(X.charAt(i - 1));     
                  
                }else if (b[i - 1][j] >= b[i][j]) {  
                       print(b, X, Y, i - 1, j);  
                } else {  
                       print(b, X, Y, i, j - 1);}  
 }