计算一个整数数组a的最长递增子序列长度的方法描述如下：
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增予序列的长度，则数组a的最长递增子序列的长度为
；其中b[i]满足最优子结构，可递归定义为：
【C代码】
下面是算法的C语言实现。
（1）常量和变量说明
a：长度为n的整数数组，待求其最长递增子序列
b：长度为n的数组，b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长
度，其中0≤i＜n
len：最长递增子序列的长度
i,j：循环变量
temp：临时变量
（2）C程序
#include＜stdio.h>
int maxL(int*b,int n){
int i,temp=0;
for(i=0;i＜n;i++){
if(b[i]>temp)
temp=b[i];
}
return temp;
}
int main（ ）{
int n,a[100],b[100],i,j,len;
scanf("%d",&n);
for(i=0;i＜n;i++){
scanf("%d",&a[i]);
}
(1);
for(i=1;i＜n;i++){
for(j=0,len=0;(2);j++){
if((3)&&len＜b[j])
len=b[j];
}
(4);
}
Printf("len:%d\n",maxL(b,n));
printf("\n");
}
【问题1】（8分）
根据说明和C代码，填充C代码中的空（1）～（4）。
【问题2】（4分）
根据说明和C代码，算法采用了（5）设计策略，时间复杂度为（6）（用O符号表示）。
【问题3】（3分）
已知数组a={3,10,5,15,6,8}，根据说明和C代码，给出数组b的元素值。
正确答案及解析
正确答案
解析
【问题1】
（1）b[0]=1
（2）j＜i
（3）a[j]＜=a[i]
（4）b[i]=len+1
【问题2】
（5）动态规划法
（6）O(n2)
【问题3】
b={1,2,2,3,3,4}
本题考查算法设计与分析技术以及算法的C语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。
（1）根据题中说明，b数组记录最长递增子序列的长，故应初始化b[0]=1，这是第一问的答案。两重for循环中，第一重是从a数组的第二个元素开始，考虑每个子数组a[0...i]的最长递增子序列的长度，第二重是具体的计算过程。考虑子数组a[0..i]，其最长递增子序列的长度应该等于子数组a[0..i-1]中的比元素a[i]小的元素的最长递增子序列的长度加1，当然，可能存在多个元素比元素a[i]小，那么存在多个最长递增子序列的长度，此时，取最大者。因此，空（2）填写“j＜i”，即考虑子数组a[0..i-1]第三问为a[j]＜=a[i]，第四问为b[i]=len+1。
（2）算法将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。使用的是动态规划的思想。时间复杂度计算最坏情况下的运算次数，最坏情况时i和j都从1跑到n,故运算n的平方次。算法的时间复杂度为O(n2)。
（3）初始b[0]=1，a[0]=3，a[1]=10进入时b[1]=2，a[2]=5进入时有3、5的序列故b[2]=2，a[3]=15进入时有3、10、15，故子序列为3，a[4]=6时有子序列3、5、6，故为3，当最后一个元素8进入时有3、5、6、8，故b[5]=4。所以b=[1,2,2,3,3,4]。
包含此试题的试卷
你可能感兴趣的试题
某软件公司项目A的利润分析如下表所示。设贴现率为10％，第二年的利润净现值是 （ ） 元。
-
- A.1,378,190
- B.949,167
- C.941,322D 922,590
- 查看答案
以下关于项目管理计划编制的理解中，正确的是（ ） 。
-
- A.项目经理应组织并主要参与项目管理计划的编制，但不应独立编制
- B.项目管理计划的编制不能采用迭代的方法
- C.让项目干系人参与项目计划的编制，增加了沟通成本，应尽量避免D 项目管理计划不能是概括的，必须是详细、具体的
- 查看答案
某软件企业2004年初计划投资1000万人民币开发一套中间件产品，预计从2005年开始，年实现产品销售收入1500万元，年市场销售成本1000万元。该产品的系统分析员张工根据财务总监提供的贴现率，制作了如下的产品销售现金流量表。根据表中的数据，该产品的动态投资回收期是 （ ） 年。
-
- A.1
- B.2
- C.2.27D 2.73
- 查看答案
软件设计过程中，视图可以从不同角度描述软件结构，以下关于几个常见视图的说法中， （ ） 是错误的。
-
- A.逻辑视图从功能需求角度描述了软件结构
- B.组件视图从实现角度描述了软件结构
- C.过程视图从质量角度描述了软件结构D 部署视图从分布问题角度描述了软件结构
- 查看答案
A project manager believes that modifying the scope of the project may provide added value service for the customer. The project manager should （ ） .
-
- A.assign change tasks to project members
- B.call A meeting of the configuration control board
- C.change the scope baseline
- D.postpone the modification until A separate enhancement project is fundeD after this project is completeD according to the original baseline
- 查看答案