OI题解｜最大上升子序列和

信息奥赛题解｜最大上升子序列和

---

🚀 题目浏览

【题目描述】

一个数的序列 $b_i$，当 $b_1<b_2<…<b_S$ 的时候，我们称这个序列是上升的。

对于给定的一个序列$(a_1,a_2,…,a_N)$，我们可以得到一些上升的子序列 $(a_{i1}, a_{i2}, …, a_{iK})$，这里 $1≤i_1<i_2<…<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(1 \le N \le 1000)$。

第二行给出序列中的 $N$ 个整数，这些整数的取值范围都在 $0$ 到 $10000$ (可能重复)。

【输出】

最大上升子序列和。

【输入样例】

7
1 7 3 5 9 4 8

【输出样例】

18

【题目来源】

https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1221

---

☘️ 题解分析

线性DP。

和「最长上升自序列」解法相同，只不过动态规划的转移方程略有不同。

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1100;
int n, sum, a[N], dp[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 线性DP
    dp[1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = a[i];
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + a[i]);
        }
    }

    // 输出最大值
    int res = -1;
    for (int i = 1; i <= n; i++) res = max(res, dp[i]);
    cout << res << endl;

    return 0;
}