【信息学奥赛一本通 C++题解】1281：最长上升子序列
信息学奥赛一本通（C++版）在线评测系统
基础算法 第一节 动态规划的基本模型
1281：最长上升子序列
小学生的课堂讲解
1. 理解题意
同学们，我们今天要解决一个有趣的问题——最长上升子序列问题。啥是上升子序列呢？比如说有这么一串数字，像1, 3, 5，后面的数字总是比前面的数字大，这就是一个上升子序列啦。那我们拿到一个长长的数字序列，要找出里面最长的那个上升子序列有多长。
举个例子，如果给我们的数字序列是1, 7, 3, 5, 9, 4, 8，这里面有很多上升子序列，像1, 7，3, 4, 8等等。我们要找出其中最长的，在这个例子里最长的上升子序列长度是 4，比如1, 3, 5, 8。所以我们的任务就是，不管给我们什么样的数字序列，都要算出它最长上升子序列的长度。
2. 解题思路
我们可以用一种像搭积木一样的方法来解决这个问题，这种方法叫动态规划。
我们先想象每个数字都有一个“小标签”，这个“小标签”记录着以这个数字结尾的最长上升子序列有多长。一开始，每个数字自己就是一个长度为 1 的上升子序列，所以每个数字的“小标签”上都先写上 1。
然后呢，我们从第二个数字开始，一个一个地看。对于每个数字，我们回头看看它前面的那些数字。要是前面有个数字比它小，那就说明可以把这个小的数字和当前数字连起来，形成一个更长的上升子序列。我们就比较一下，是原来这个数字“小标签”上的长度长，还是前面那个小数字“小标签”上的长度加 1 长，把长的那个写在当前数字的“小标签”上。
最后，我们看看所有数字的“小标签”，找出最大的那个数字，这个数字就是整个序列最长上升子序列的长度啦。
3. 解题步骤
- 第一步：输入数字序列：我们要先知道有多少个数字，然后把这些数字一个一个地记下来。
- 第二步：给每个数字的“小标签”初始化：让每个数字的“小标签”都写上 1，因为每个数字自己就是长度为 1 的上升子序列。
- 第三步：更新“小标签”：从第二个数字开始，一个一个地看，对于每个数字，看看它前面比它小的数字，更新它的“小标签”。
- 第四步：找出最长的长度：看看所有数字的“小标签”，找出最大的那个，这就是我们要的答案。
4. C++代码实现
#include <iostream> // 包含输入输出流的头文件，这样我们就能从键盘输入数字，把结果输出到屏幕上啦
using namespace std;
int main() {
int n; // 定义一个变量 n，用来存数字序列里有多少个数字
cin >> n; // 从键盘输入数字的个数，存到 n 里
int a[1005]; // 定义一个数组 a，用来存数字序列，最多能存 1005 个数字
int dp[1005]; // 定义一个数组 dp，这就是我们说的“小标签”数组，用来存以每个数字结尾的最长上升子序列的长度
// 输入数字序列，并给“小标签”初始化
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 从键盘输入一个数字，存到数组 a 的第 i 个位置
dp[i] = 1; // 把“小标签”数组 dp 的第 i 个位置初始化为 1
}
// 更新“小标签”
for (int i = 2; i <= n; i++) { // 从第二个数字开始看
for (int j = 1; j < i; j++) { // 看看当前数字前面的所有数字
if (a[j] < a[i]) { // 如果前面的数字 a[j] 比当前数字 a[i] 小
// 比较 dp[i] 和 dp[j] + 1 的大小，把大的那个存到 dp[i] 里
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int ans = 0; // 定义一个变量 ans，用来存最长上升子序列的长度，先初始化为 0
// 找出“小标签”数组里的最大值
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]); // 比较 ans 和 dp[i] 的大小，把大的那个存到 ans 里
}
cout << ans << endl; // 把最长上升子序列的长度输出到屏幕上
return 0;
}
5. 知识点总结
- 数组：就像我们的“小仓库”，可以把很多东西（这里是数字）一个一个地放进去，还能按照顺序找到它们。我们用
a数组存数字序列，用dp数组存每个数字对应的“小标签”。 - 循环：循环就像一个小机器人，会按照我们的要求重复做一些事情。这里用了两层循环，外层循环一个一个地看数字，内层循环回头看前面的数字，这样就能更新每个数字的“小标签”啦。
- 动态规划：这是一种很厉害的解题方法，把大问题分成很多小问题，先解决小问题，再从这些小问题的答案里找到大问题的答案。在这个问题里，我们先算出每个数字对应的最长上升子序列长度，再从这些长度里找出最大的，就是整个序列的最长上升子序列长度啦。
- 比较大小：用
max函数来比较两个数的大小，找出大的那个数。这样就能更新“小标签”和最终的答案啦。