3662. 最大上升子序列和

给定一个长度为 nn 的整数序列 a1,a2,…,ana1,a2,…,an。

请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。

请问这个最大值是多少？

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an。

输出格式

输出最大的上升子序列和。

数据范围

对于前三个测试点，1≤n≤41≤n≤4。
对于全部测试点，1≤n≤105,1≤ai≤1091≤n≤105,1≤ai≤109。

输入样例1：

2
100 40

输出样例1：

100

输入样例2：

4
1 9 7 10

输出样例2：

20

样例解释

对于样例 11，我们只选取 100100。

对于样例 22，我们选取 1,9,101,9,10。

算法 —— 离散化 + 树状数组
用 sum[i] 表示以 a[i] 为结尾的最大单调子序列和
用 maxSum[x] 表示以 x 为结尾值的最大单调子序列和

暴力解法:

for (int i = 1; i <= n; i++) {
    sum[i] = a[i];
    for (int j = 1; j < a[i]; j++) {
        sum[i] = max(sum[i], maxSum[j] + a[i]);
    }
    maxSum[a[i]] = max(maxSum[a[i]], sum[i]);
}

可以使用树状数组优化，将 maxSum 优化成单点修改、区间查询的树状数组。
需要注意的是，数据的范围为 1e9，比较大，还需要进行离散化。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL n, a[N], b[N], sum[N], maxSum[N];
unordered_map<int, LL> mp;
LL c[N];
// 查询前缀和：查询序列 a 第 1~x 个数的和
LL ask(LL x) {
    LL ans = 0;
    for (; x; x -= x & -x) ans = max(ans, c[x]);
    return ans;
}
// 单点增加：给序列中的一个数 a[x] 加上 y
// 算法：自下而上每个节点都要增加 y
void add(int x, LL y) {
    for (; x <= n; x += x & -x) c[x] = max(c[x], y);
}

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

    // 离散化
    memcpy(b, a, sizeof a);
    sort(b + 1, b + n + 1);
    LL m = 0;
    for (int i = 1; i <= n; i++) {
        if (!mp.count(b[i]))
            mp[b[i]] = ++m;
    }

    // DP 过程，使用树状数组优化
    for (int i = 1; i <= n; i++) {
        sum[i] = max(mp[a[i]], ask(mp[a[i]] - 1) + a[i]);
        add(mp[a[i]], sum[i]);
        // sum[i] = a[i];
        // for (int j = 1; j < a[i]; j++) {
        //     sum[i] = max(sum[i], maxSum[j] + a[i]);
        // }
        // maxSum[a[i]] = max(maxSum[a[i]], sum[i]);
    }

    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, sum[i]);
    }
    cout << ans << endl;
    return 0;
}