我们称序列Z=z1z2zk是序列X=x1x2xm的子序列当且仅当存在严格上升的序列i1i2ik使得对j=12k有xij=zj。比如Z=abfc 是X=abcfbc的子序列。 现在给出两个序列X和Y你的任务是找到X和Y的最大公共子序列也就是说要找到一个最长的序列Z使得Z既是X的子序列也是Y的子序列。

思路：

最长公共子序列（LCS）是动态规划中经典的问题，可以使用动态规划算法解决。定义dp[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度。则有以下状态转移方程：

dp[i][j] = 0, (i=0或j=0) dp[i][j] = dp[i-1][j-1]+1, (xi=yj) dp[i][j] = max(dp[i-1][j], dp[i][j-1]), (xi!=yj)

最后dp[m][n]即为序列X和Y的最长公共子序列的长度。

为了求出具体的最长公共子序列，可以在动态规划过程中记录路径。具体地，使用一个二维数组path[i][j]，若dp[i][j]是由dp[i-1][j-1]+1转移而来，则path[i][j]为"↖"；若dp[i][j]是由dp[i-1][j]转移而来，则path[i][j]为"↑"；若dp[i][j]是由dp[i][j-1]转移而来，则path[i][j]为"←"。最后，从path[m][n]开始，根据箭头的方向依次输出最长公共子序列的元素即可。

代码实现：