NOIP 提高 2013 第一轮 第 25 题：最长上升子序列长度（LIS）

题目

```
#include <stdio.h> 
const int SIZE = 100; 
int main()  
{ 
 int height[SIZE], num[SIZE], n, ans; 
 int i, j; 
 scanf("%d", &n); 
 for (i = 0; i < n; i++) { 
  scanf("%d", &height[i]); 
  num[i] = 1; 
  for (j = 0; j < i; j++) { 
   if ((height[j] < height[i]) && (num[j] >= num[i]))  
    num[i] = num[j]+1; 
  } 
 } 
 ans = 0; 
 for (i = 0; i < n; i++) { 
  if (num[i] > ans) ans = num[i]; 
 } 
 printf("%d\n", ans); 
 return 0; 
} 
```
输入：   
8   
3 2 5 11 12 7 4 10   
输出：_________

请写出程序的输出结果。

答案

4

题解

考点定位

本题考「LIS 模拟」,对应大纲 4.3.2 动态规划（难度【3】）。

解题过程

num[i] = 以 height[i] 结尾的最长上升子序列长。按原卷输入逐项递推取 max：

答案：4。

易错提醒

① O(n²) 递推：num[i]=max(num[j])+1（j<i, h[j]<h[i]）；② 手算列表不易错。