Question

谁给个求最长公共子序列的算法？

Answer 1

首先告诉你个百度账号叫pyx1997的人。他教会了我，现在让我来教会你。
我们来看一组数据：
40 100 50 60 70
好，让我们手动计算一下：
如果我们纯贪心的话：高个i变量直接从头到尾循环：到i=2时，就求得maxlen=2。i=5，maxlen被更新为3。但是我们看得出：最长不降子序列为40 50 60 70，maxlen=4。
为什么，为什么贪心会导致如此结果？那就是因为贪心童鞋的生理缺陷：目光短浅！
好了，让我们在重新审题。
此时因为我们的最长不降子序列同时要求“最长”和“不降”这两个方面，又因为我们的眼光要放长远，所以我们选择了用一个数组来记录以当前为起点的最长不降子序列。酱紫的话，我们就把这个大问题分成来若干个小问题。又因为如果我们顺退的话，我们不能确定到底是怎么样才算最长，前面的长度总是依赖于后面的长度。所以我们选择倒推。
a:原始数据的存放数组。
f:状态数组，即为以i(1<=i<=n)为起点的最长不降子序列的长度。不用设初值。
由于我不知道LZ使用的是什么语言，所以这里给出伪代码：
for i←n downto 1 //DP的次数
[maxlen←0 //将maxlen置空
for j←n downto i+1 //二重循环：比较i后的已知的最长不降子序列的长度。
if (f[j]>maxlen)&(a[i]>=a[j]) then maxlen←f[j] //求出最大值
f[i]←maxlen+1] //将最大值+1放入f[i]
然后，我们再将F数组扫描一遍，取最大值，即为答案。
如果要求序列的话，可以另开一个存放下一个值的数组next，然后再循环的最后加上一句next[i]←j
算法描述完毕。具体的细节请自行调试。本人打的很辛苦，望lz给分。