NOIP 普及组初赛 · 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

看到 num[i]=1 且循环内 num[i]=num[j]+1 → 最长上升子序列长度

误把 num[i] 初始值当 0 会少算 1；误看 height[j]<height[i] 为大于号会算下降子序列

考点：最长上升子序列（LIS）

程序在做什么

输入 n 个高度，对每个位置 i，向前扫描所有 j<i，若 height[j]<height[i] 则 num[i] 更新为 num[j]+1，最终输出 num 数组的最大值。