（单选题）
给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1Am[i]=1+max{0，m[k]（A[k]Bm[i]=1+m[k]（k=i-1&&i>1）
Cm[i]=1+max{0，m[k]（A[k]≤A[i]，1≤kDm[i]=max{0，m[k]（A[k]
正确答案
答案解析
略
Am[i]=1+max{0，m[k]（A[k] Bm[i]=1+m[k]（k=i-1&&i>1） Cm[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k Dm[i]=max{0，m[k]（A[k]
正确答案
答案解析
略
相似试题
（简答题）
给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
（简答题）
考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2就直接求解。否则，将序列等分成两个子序列A[1..n/2]和A[n/2+1..n]，分别找出这两子序列的最大最小元素x1，y1和x2，y2；然后据此求出A[1..n]的最大元素x=max{x1，x2}及最小元素y=min{y1，y2}。请给出该算法计算时间T（n）满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k为正整数）。
（简答题）
以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。
（简答题）
请编一个函数fun（int *a，int n，int *odd，int *even），函数的功能是分别求出数组中所有奇数之和以及所有偶数之和。形参n给出数组a中数据的个数；利用指针odd返回奇数之和，利用指针even返回偶数之和。例如：数组中的值依次为：1，9，2，3，11，6；则利用指针odd返回奇数之和24；利用指针even返回偶数之和8。
（判断题）
有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）]*（2n）!/[（n!）*（n!）]。
（简答题）
在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。 输入数据的第1行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。（贪心算法，要求给出贪心策略）
（简答题）
求s=a+aa+aaa+...+aa...a（n个）的值，其中a是一个数字（1--9），n表示a的位数，a和n由键盘输入。
（简答题）
给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。
（单选题）
若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。
