【信息学奥赛一本通 C++题解】1285：最大上升子序列和

信息学奥赛一本通（C++版）在线评测系统
基础算法 第一节 动态规划的基本模型
1285：最大上升子序列和

---

“最大上升子序列和”问题课堂讲解

1. 理解题意

同学们，想象我们有一串数字，就像一串彩色的珠子，每个珠子上都标着一个数字，这就是题目里说的序列。比如有这样一串数字：(1)，(7)，(3)，(5)，(9)，(4)，(8)。

现在我们要从这串数字里挑出一些数字，这些数字要满足后面的数字比前面的数字大，这样挑出来的数字组成的新序列就叫上升子序列。比如说从上面那串数字里挑出(1)，(3)，(5)，(9)，这就是一个上升子序列。

我们的任务是在所有能挑出来的上升子序列里，找到数字加起来和最大的那个上升子序列，然后把这个最大的和告诉大家。要注意哦，最长的上升子序列，它的数字和不一定是最大的。就像数字序列(100)，(1)，(2)，(3)，最长的上升子序列是(1)，(2)，(3)，但是数字和最大的上升子序列是(100)，因为(100)比(1 + 2 + 3)的和要大。

2. 解题思路

我们可以用一种像搭积木一样的方法来解决这个问题，这种方法叫动态规划。

我们先给每个数字都想象有一个“小背包”，这个“小背包”里装着以这个数字结尾的最大上升子序列的和。一开始，每个数字自己就是一个长度为(1)的上升子序列，所以每个数字“小背包”里的和就是它自己的值。

然后呢，我们从第二个数字开始，一个一个地看。对于每个数字，我们回头看看它前面的那些数字。要是前面有个数字比它小，那就说明可以把这个小的数字和当前数字连起来，形成一个新的上升子序列。我们就把前面那个小数字“小背包”里的和，加上当前数字，得到一个新的和。我们比较一下，是原来这个数字“小背包”里的和大，还是新得到的和大，把大的那个存到当前数字的“小背包”里。

最后，我们看看所有数字的“小背包”，找出里面最大的那个和，这个和就是我们要找的最大上升子序列的和啦。

3. 解题步骤

1. 输入数字序列：我们要先知道这串数字有多少个，也就是输入序列的长度(N)。然后把这串数字里的每个数字都一个一个地记下来，存到一个数组里。
2. 初始化“小背包”：让每个数字的“小背包”（也就是存储以该数字结尾的最大上升子序列和的数组）里都先装上它自己的值，因为每个数字自己就是长度为(1)的上升子序列，和就是它本身。
3. 更新“小背包”：从第二个数字开始，一个一个地看，对于每个数字，看看它前面比它小的数字，把前面小数字“小背包”里的和加上当前数字，和原来当前数字“小背包”里的和比较，把大的那个存到当前数字的“小背包”里。
4. 找出最大和：看看所有数字的“小背包”，找出里面最大的那个和，这就是我们要的答案。

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] = a[i]; // 把“小背包”数组 dp 的第 i 个位置初始化为当前数字 a[i]}// 更新“小背包”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] + a[i] 的大小，把大的那个存到 dp[i] 里dp[i] = max(dp[i], dp[j] + a[i]);  }}}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. 知识点总结

1. 数组：我们用了两个数组，(a)数组存原始的数字序列，(dp)数组存每个数字对应的“小背包”里的和。数组就像一个小抽屉，我们可以把很多东西（这里是数字）一个一个地放进去，还能按照顺序找到它们。
2. 循环：循环就像一个勤劳的小工人，会按照我们的要求重复做一些事情。这里用了两层循环，外层循环一个一个地看数字，内层循环回头看前面的数字，这样就能更新每个数字的“小背包”啦。
3. 动态规划：这是一种很厉害的解题方法，把大问题分成很多小问题，先解决小问题，再从这些小问题的答案里找到大问题的答案。在这个问题里，我们先算出每个数字对应的最大上升子序列的和，再从这些和里找出最大的，就是整个序列的最大上升子序列的和啦。
4. 比较大小：用(max)函数来比较两个数的大小，找出大的那个数。这样就能更新“小背包”里的和以及最终的最大和答案啦。