【题目大意】

给定一个数组，让你去求最大的 / 上升 / 子序列 / 之和，是一道经典的 dp（动态规划）题。

【样例解读】

上升子序列有：1 7，3 4 8，1 3 5 9，1，7，3，5，9，4，8。

它们的和分别为：8，15，18，1，7，3，5，9，4，8。

显然，最大的为 $18$，答案就是 $18$。需要注意的是，每个元素都可以作为一个上升子序列。

【思路分析】

既然是一道 dp，那么我们需要：

1. $\color{red}{\texttt{终止条件}}$：其实就是每个元素都可以作为一个上升子序列。

2. $\color{red}{\texttt{状态转移方程}}$：现在假设有元素下标 $i$ 和比他小的元素下标 $j$，我们是不是可以用 $dp_k$ 来存储以第 $k$ 个元素结尾的最大上升子序列和呢？如果下标 $i$ 对应的元素比 $j$ 对应的元素大，那么 $a_i$ 就可以接在以 $a_j$ 结尾的上升子序列后面，成为新的结尾，就用 $dp_i$ 存储。于是乎，可以判断当前以第 $i$ 个元素结尾的最大上升子序列和与 $a_i$ 加入 $dp_j$ 的最大上升子序列和谁大，从而改变 $dp_i$，就有了 dp[i] = max(dp[i], a[i] + dp[j])。

是不是答案一下子就出来了？

【代码分析】

结合以上三个板块，代码可以分 $4$ 个步骤解决:

1. 定义状态：我们使用一个数组 $dp$，其中 $dp_i$ 表示以第 $i$ 个元素结尾的‌最大上升子序列和‌。例如，如果序列是 $[1, 7, 3, 5, 9, 4, 8]$，那么 $dp_5$ 表示以 $9$ 结尾的最大上升子序列和。

2. 初始化：每个元素本身都可以作为一个长度为 $1$ 的上升子序列，所以：

dp[i] = a[i];

3. 状态转移：对于每个 $i$，我们遍历它前面的所有元素 $j(j<i)$，如果 $a_i>a_j$，说明可以将 $a_i$ 接在以 $a_j$ 结尾的上升子序列后面：

if (a[i] > a[j]){ 
    dp[i] = max(dp[i], a[i] + dp[j]); //状态转移方程 
}   

这样，我们就可以不断更新 $dp_i$，使其保持为以 $a_i$ 结尾的最大上升子序列和。

然后再在 $dp$ 数组中找最大值，即为所求的最大上升子序列和。

4. 输出答案：将答案输出。

【PS】：如果你想要高大上的代码，你可以将 $a$ 数组清空为 $k$ 的代码写为：memset(数组名（a）, 要清空成为的数（k）, sizeof(数组名（a）));。比如：memset(array, 0, sizeof(a));。

AC Code（有注释）

算法复杂度：$O(n^2)$。

//from RDS 2026020510:55 TJ A245
#include<bits/stdc++.h>
#define int long long //不开longlong见祖宗
using namespace std;
signed main(){
	int n, a[1005]; //输入的n和a数组
	memset(a, 0, sizeof(a)); //将a数组清空为0
	cin >> n; //读入数据n
	int dp[1005]; //dp数组：dp[i]表示以i结尾的最大上升子序列和
	memset(dp, 0, sizeof(dp)); //将dp数组清空为0
	for (int i = 1; i <= n; i++){ //读入a数组
		cin >> a[i]; //读入a[i]
		dp[i] = a[i]; //每个元素都可以作为一个上升子序列
	}
	int ans = 0; //记录结果
	for (int i = 1; i <= n; i++){ //遍历每个元素，dp解决问题
		for (int j = 1; j <= i; j++){ //遍历比i下标小的元素
			if (a[i] > a[j]){ //如果a[i] > a[j]，说明可以将a[i]接在以a[j]结尾的上升子序列后面
				dp[i] = max(dp[i], a[i] + dp[j]); //状态转移方程 
			}
		}
		ans = max(ans, dp[i]); //每次不断更新结果
	}
	cout << ans << endl; //输出结果
	return 0;
}
/*
in
7
1 7 3 5 9 4 8
out
18
*/

AC Code（无注释）

//from RDS 2026020510:55 TJ A245
#include<bits/stdc++.h>
#define int long long 
using namespace std;
signed main(){
	int n, a[1005]; 
	memset(a, 0, sizeof(a));
	cin >> n; 
	int dp[1005]; 
	memset(dp, 0, sizeof(dp)); 
	for (int i = 1; i <= n; i++){ 
		cin >> a[i]; 
		dp[i] = a[i]; 
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){ 
		for (int j = 1; j <= i; j++){
			if (a[i] > a[j]){
				dp[i] = max(dp[i], a[i] + dp[j]); 
			}
		}
		ans = max(ans, dp[i]); 
	}
	cout << ans << endl; 
	return 0;
}

测试正确证明📝

如有错误，请各位大佬指出，🦀🦀。