共48道题，当前是第11题

初赛真题

01 #include <iostream>
02 using namespace std;
03 int main() {
04     const int SIZE = 100;
05     int height[SIZE], num[SIZE], n, ans;
06     cin >> n;
07     for (int i = 0; i < n; i++) {
08         cin >> height[i];
09         num[i] = 1;
10         for (int j = 0; j < i; j++) {
11             if ((height[j] < height[i]) && (num[j] >= num[i]))
12             num[i] = num[j] + 1;
13         }
14     }
15     ans = 0;
16     for (int i = 0; i < n; i++) {
17         if (num[i] > ans) ans = num[i];
18     }
19     cout << ans << endl;
20     return 0;
21 }

1. B。
2. A。
3. B。
4. A。
5. B。
6. C。

这段代码是在求最长上升子序列，比较简单。代码中将每个位置的字符储存在 $height$ 数组中，对于每个 $i$ 维护 $num[i]$ 表示以 为最后一个点的最长上升子序列。求答案时遍历 $num $数组取最大值即可。需要注意的一点就是因为代码中是从 $0$ 开始储存数据的，所以这份代码可以接受 $n <= 100$ 的输入。

Question

1. 最大可以为 99 才能保证程序不会出错误。( )

2. 程序功能：输入长度为 n 的整数序列，求最长上升子序列的长度。( )

3. 若将第 10 行的 j < i 改为 j <= i ，程序运行时会发生错误。( )

4. 本程序的时间复杂度为 $O(n^2)$

5. 若输入
6
2 5 3 11 12 4
则输出为( )

6. 若输入
5
2 3 4 5 6
则第 12 行 num[i] = num[j] + 1; 执行( )次