【题目来源】
AcWing：1016. 最大上升子序列和 - AcWing题库
【题目描述】
一个数的序列 \(b_i\)，当 \(b_1\lt b_2\lt \dots \lt b_S\) 的时候，我们称这个序列是上升的。
对于给定的一个序列(\(a_1,a_2,\dots,a_N\))，我们可以得到一些上升的子序列(\(a_{i_1},a_{i_2},\dots,a_{i_K}\))，这里 \(1\le i_1\lt i_2 \lt \dots \lt i_K\le N\)。
比如，对于序列(\(1,7,3,5,9,4,8\))，有它的一些上升子序列，如(\(1,7\)),(\(3,4,8\))等等。
这些子序列中和最大为\(18\)，为子序列(\(1,3,5,9\))的和。
你的任务，就是对于给定的序列，求出最大上升子序列和。
注意，最长的上升子序列的和不一定是最大的，比如序列(\(100,1,2,3\))的最大上升子序列和为\(100\)，而最长上升子序列为(\(1,2,3\))。
【输入】
输入的第一行是序列的长度\(N\)。
第二行给出序列中的\(N\)个整数，这些整数的取值范围都在\(0\)到\(10000\)(可能重复)。
【输出】
输出一个整数，表示最大上升子序列和。
【输入样例】
7
1 7 3 5 9 4 8
【输出样例】
18
【解题思路】
【算法标签】
《AcWing 1016 最大上升子序列和》 #DP# #线性DP# #最长上升子序列#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 1010; // 数列长度最大为1000// 定义全局变量
int a[N], f[N], n; // a[N]: 存储输入的数列，f[N]: f[i]表示以a[i]作为结尾的上升子序列的最大和，n: 数列的长度// 主函数，程序的入口点
int main()
{// 读取数列的长度 ncin >> n;// 循环读取数列的每个元素，并存储到数组 a[i] 中，索引从 1 开始for (int i = 1; i <= n; i++) cin >> a[i]; // 读入数列// =============================// 动态规划部分：计算以每个元素 a[i] 作为结尾的上升子序列的最大和// =============================for (int i = 1; i <= n; i++) // 遍历每个元素 a[i] 作为结尾{// 初始化以 a[i] 作为结尾的上升子序列的最大和为 a[i] 自身（即子序列只包含 a[i]）f[i] = a[i];// 遍历 a[i] 之前的所有元素 a[j]，寻找可以接在 a[i] 前面的元素for (int j = 1; j < i; j++) {// 如果元素 a[j] 的值小于元素 a[i] 的值，表示可以形成上升子序列if (a[j] < a[i]) // a[j]、a[i] 是上升序列// 更新以 a[i] 作为结尾的上升子序列的最大和为 f[j] + a[i] 和当前 f[i] 中的较大值f[i] = max(f[i], f[j] + a[i]);}} // =============================// 计算并输出最大的上升子序列的和// =============================// 初始化结果变量 ans，用于记录最大的上升子序列的和int ans = 0;// 遍历所有元素，计算以每个元素 a[i] 作为结尾的上升子序列的最大和，并更新 ansfor (int i = 1; i <= n; i++) // 更新 ans 为 f[i] 和当前 ans 中的较大值ans = max(ans, f[i]);// 输出最大的上升子序列的和cout << ans << endl;// 程序正常结束，返回 0return 0;
}
【运行结果】
7
1 7 3 5 9 4 8
18