NOIP 普及 2013 第一轮 第 26 题：动态规划求最长上升子序列长度

题目

```
#include <iostream> 
using 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;
}
```
输入：  
6  
2 5 3 11 12 4

阅读程序写结果：

答案

4

题解

考点定位

本题考「最长上升子序列模拟」,对应大纲 4.3.2 动态规划（难度【3】）。

解题过程

程序求 LIS 长度：num[i] = 以 height[i] 结尾的 LIS 长度，ans 取最大。按原卷输入序列逐项递推，ans=4（例如 3,5,11,12 或 2,5,7,10 等长 4 的上升段）。

答案：4。

易错提醒

① O(n²) LIS：num[i] = max(num[j]+1)（j<i 且 h[j]<h[i]）；② 手算时逐项写 num 值再取 max，不易错。