1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。
（简答题）
给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
正确答案
假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]x[i]，j∈S}。于是状态k应从S中删去。
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。
答案解析
略
相似试题
（单选题）
给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1
（简答题）
对于给定的一个序列（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）。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。
（简答题）
给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。
（简答题）
给定由n个整数（其中可能有负数）组成的序列a1，a2，...an，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为： 动态规划解决方案：记，则对于n个整数序列的最大子段和问题，即为所求。 动态规划递归式： 问：对于实例：（a1，a2，...a6）＝（－2，11，－4，13，－5，－2）按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b数组中的数值，和最大子段和的值。
（简答题）
以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。
（判断题）
有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）]*（2n）!/[（n!）*（n!）]。
（填空题）
一个串的任意个连续的字符组成的子序列称为该串的（），包含该子串的串称为（）。
（简答题）
（1）设根为第1层，对给定权值1，3，4，4，5，6，构造深度为5的哈夫曼树。 提示：构造中当出现被选的结点值有多个相等时，可尝试不同组合，以得到要求的树的深度。 （2）求树的带权路径长度。 （3）给出对上述哈夫曼树中序遍历得到的的序列 （4）一棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由？
（简答题）
试证明：若借助栈由输入序列12…n得到的输出序列为p1p2…pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i＜j＜k使pj＜pk＜pi。
