问答题
阅读下列说明和C代码，回答下面问题。
[说明]
计算一个整数数组a的最长递增子序列长度，对其方法描述如下。
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为max(0≤i＜n){b[i]}，其中b[i]满足最优子结构，可递归定义为：
[说明]
计算一个整数数组a的最长递增子序列长度，对其方法描述如下。
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为max(0≤i＜n){b[i]}，其中b[i]满足最优子结构，可递归定义为：
问答题
根据说明和C代码，填充C代码中的空。
【正确答案】
【答案解析】本题考查最长递增序列问题，是一种动态规划法，也考查时间复杂度的计算。
b[0]=1
j＜=i
a[j]＜=a[i]
b[i]=len+1 [解析] 本题考查算法设计、分析技术以及算法的C语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。
根据题中说明，b数组记录最长递增子序列的长，故应初始化b[0]=1，这是第一问的答案，初始Len=0，接下来a中某个元素的值大于前面某个元素，则Len+1放进b，故第二问为j＜=i，第四问为b[i]=Len+1。
b[0]=1
j＜=i
a[j]＜=a[i]
b[i]=len+1 [解析] 本题考查算法设计、分析技术以及算法的C语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。
根据题中说明，b数组记录最长递增子序列的长，故应初始化b[0]=1，这是第一问的答案，初始Len=0，接下来a中某个元素的值大于前面某个元素，则Len+1放进b，故第二问为j＜=i，第四问为b[i]=Len+1。
问答题
根据说明和C代码，算法采用了______设计策略，时间复杂度为______(用O符号表示)。
【正确答案】
【答案解析】动态规划法
O(n 2 ) [解析] 算法将待求解问题分解成若干个子问题，先求子问题，然后从这些子问题的解中得到原问题的解，使用的是动态规划的思想，时间复杂度计算最坏情况下的运算次数，最坏情况时i和j都从1跑到n，故运算n的平方次，算法的时间复杂度为O(n 2 )。
O(n 2 ) [解析] 算法将待求解问题分解成若干个子问题，先求子问题，然后从这些子问题的解中得到原问题的解，使用的是动态规划的思想，时间复杂度计算最坏情况下的运算次数，最坏情况时i和j都从1跑到n，故运算n的平方次，算法的时间复杂度为O(n 2 )。
问答题
已知数组a={3,10,5,15,6,8}，据说明和C代码，给出数组b的元素值。
【正确答案】
【答案解析】σ={1,2,2,3,3,4}[解析] 初始化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]。