最长递增子序列
【实验目的】
1 掌握动态规划和 LCS 的相关算法
2 利用动态规划的思想实现最长递增子序列
3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到 O(nlgn)
【系统环境】
Windows XP 平台
【实验工具】
VC++6.0 英文企业版
【实验原理】（若涉及算法设计）
描述： 随机生成小于等于 n 的自然数的一个序列，输出其最长递增子序列（任意一个即可）。
n 分别取 1000，3000，10000。
例： n=5 随机序列为 5 1 4 2 3，正确输出为 1 2 3，即长度为 3 的递增子序列。
分析：
1 使用动态规划的前提条件：要求一个序列的最大递增子序列最优解问题可以转化为求其子问题的最优解
问题，而且其子问题包含重叠的子问题比如此题 1 2 3 这个序列包含 1 2 这个序列，我们可以通过查找计
算。(注意子序列可能不唯一)
2 仿照 LCS 问题，a 存放随机生成长度为 n 的数组元素。构造一个数组 f，它的每一个值存放以 a [i]元素
为结尾的最长子序列的长度，则此问题的递归关系式如下：
f[i]= 1 if i=0
else
(当满足 a[j]<a[i]取出这些 f[j]并查找最大值,如果没有 max f[j]为 0)
3 解释：在 a[i]前面找到满足 a[j]<a[i]的最大 f[j],然后把 a[i]接在它的后面(用 pre 记录前一个数的下标)，
可得到 a[i]的最长递增子序列的长度，或者 a[i]前面没有比它小的 a[j]，那么这时 a[i]自成一序列（它的
pre[i]=-1），长度为 1.最后整个数列的最长递增子序列即为 max(f[j]| 0<=j<=n-1);
评论10