阅读程序题1
#includeusing namespace std; int main() { const int SIZE = 100; int height[SIZE], num[SIZE], n, ans; cin >> n; for (int i = 0; i < n; i++) { cin >> height[i]; num[i] = 1; for (int j = 0; j < i; j++) { if ((height[j] < height[i]) && (num[j] >= num[i])) num[i] = num[j] + 1; } } ans = 0; for (int i = 0; i < n; i++) { if (num[i] > ans) ans = num[i]; } cout << ans << endl; return 0; }
n 最大可以为 99 才能保证程序不会出错误。()
程序功能:输入长度为 n 的整数序列,求最长上升子序列的长度。()
若将第 9 行的 j < i 改为 j <= i ,程序运行时会发生错误。( )
本程序的时间复杂度为O(n2).( )
若输入
6
2 5 3 11 12 4
则输出为( )
3
4
2
5
若输入
5
2 3 4 5 6
则第 12 行 num[i] = num[j] + 1; 执行( )次。
6
8
10
12
发表评论