编辑代码

public class MaxCommonSubsequence {  
    public static String maxCommonSubsequence(String X, String Y) {  
        int m = X.length();  
        int n = Y.length();  
        int[][] dp = new int[m + 1][n + 1];  
        for (int i = 1; i <= m; i++) {  
            for (int j = 1; j <= n; j++) {  
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {  
                    dp[i][j] = dp[i - 1][j - 1] + 1;  
                } else {  
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  
                }  
            }  
        }  
        StringBuilder sb = new StringBuilder();  
        int i = m, j = n;  
        while (i > 0 && j > 0) {  
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {  
                sb.append(X.charAt(i - 1));  
                i--;  
                j--;  
            } else if (dp[i - 1][j] > dp[i][j - 1]) {  
                i--;  
            } else {  
                j--;  
            }  
        }  
        return sb.reverse().toString();  
    }  

     public static void main(String[] args) {  
        // 测试用例1  
        String X = "abcde";  
        String Y = "ace";  
        String result1 = MaxCommonSubsequence.maxCommonSubsequence(X, Y);  
        System.out.println("测试用例1：最大公共字符串子序列：" + result1); // 输出：ace  
  
        // 测试用例2  
        String X2 = "abc";  
        String Y2 = "ab";  
        String result2 = MaxCommonSubsequence.maxCommonSubsequence(X2, Y2);  
        System.out.println("测试用例2：最大公共字符串子序列：" + result2); // 输出：ab  
  
        // 测试用例3  
        String X3 = "axc";  
        String Y3 = "abc";  
        String result3 = MaxCommonSubsequence.maxCommonSubsequence(X3, Y3);  
        System.out.println("测试用例3：最大公共字符串子序列：" + result3); // 输出：ac或c（两种可能的最长公共子序列）  
  
        // 测试用例4  
        String X4 = "abc";  
        String Y4 = "bca";  
        String result4 = MaxCommonSubsequence.maxCommonSubsequence(X4, Y4);  
        System.out.println("测试用例4：最大公共字符串子序列：" + result4); // 输出：无（没有公共子序列）  
    }  

}