即，f（i）是从f（1），f（2），……到f（i-1）中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。
最后，所要求的整个序列的最长公共子序列长度为max{f（i）：1<=i<=n}
（简答题）
对于给定的一个序列（a1，a2，...aN），1≤N≤1000。我们可以得到一些递增上升的子序列（ai1，ai2，...aiK），这里1≤i1〈i2〈...iK≤N。比如，对于序列（1，7，3，5，9，4，8），有它的一些上升子序列，如（1，7），（3，4，8）等等。这些子序列中最长的长度是4，比如子序列（1，3，5，8）。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。
正确答案
设f（i）表示：从左向右扫描过来直到以a[i]元素结尾的序列，获得的最长上升子序列的长度，且子序列包含a[i]元素（1≤i≤n）。
即，f（i）是从f（1），f（2），……到f（i-1）中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。
最后，所要求的整个序列的最长公共子序列长度为max{f（i）：1<=i<=n}
即，f（i）是从f（1），f（2），……到f（i-1）中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。
最后，所要求的整个序列的最长公共子序列长度为max{f（i）：1<=i<=n}
答案解析
略
相似试题
（简答题）
给定由n个整数（其中可能有负数）组成的序列a1，a2，...an，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为： 动态规划解决方案：记，则对于n个整数序列的最大子段和问题，即为所求。 动态规划递归式： 问：对于实例：（a1，a2，...a6）＝（－2，11，－4，13，－5，－2）按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b数组中的数值，和最大子段和的值。
（填空题）
假定AB为一个类，有类AB的两个对象a1，a2；则执行语句AB*a[10]={&a1，&a2}；时系统自动调用该类的构造函数的次数为（）。
（单选题）
给定关系R（A1，A2，A3，A4）上的函数依赖集F={A1→A2，A3→A2，A2→A3，A2→A4}，R的候选关键字为（）
（填空题）
线性有序表（a1，a2，a3，，，a10）按关键字从小到大排列，对一个给定的关键字值k，用二分法查找表中关键字与k相等的元素，在查找不成功的情况下，最多需要查找（）次。
（简答题）
给定一序列试a1，a2，…，an，利用合并排序对序列按升序进行排序，编程实现。
（填空题）
小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而…… a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有（）种。
（简答题）
已知线性表A={a1、a2、……an}采用链接存储结构，其数据域由4个值域组成，假设依次为 从单链表的表头删除一个结点。
（简答题）
给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。
（单选题）
下列命令序列的执行结果是（）A="2000"B1="1"A1=A+B1？A1
