算法

(离散化,树状数组) $O(n \log n)$

众所周知，与求上升子序列相关的优化一般有两种：

1. 单调栈 & 二分优化
2. 线段树 | 树状数组 | 平衡树等数据结构优化

这里求的是上升子序列中所有元素的和的最大值，不太好用单调栈+二分，故想到用树状数组。

可能有些人对数据结构优化最长上升子序列不太了解，这里说一下思路。

先考虑暴力DP：设 $f[i]$ 表示在 $a _ 1 \sim a _ i$ 中，且以 $a _ i$ 结尾的所有上升子序列中，元素和的最大值。

有转移方程：

$$ f[i] = a _ i + \max _ {0 \leq j < i, a _ j < a _ i} f[j] $$

将序列 $a$ 离散化，考虑优化对 $f _ i$ 的转移。

设 $g _ x$ 表示所有 $j < i$ 且 $a _ j = x$ 的 $f _ j$ 的最大值，那么 $\begin {aligned} \max _ {0 \leq j < i, a _ j < a _ i} f[j] \end {aligned}$ 就等于 $\begin {aligned} \max _ {x < a _ i} g _ x \end {aligned}$，注意到这项是 $g$ 的一个前缀最大值，这恰可以用树状数组动态维护。

具体可见代码。

时间复杂度

离散化 $O(n \log n)$，树状数组 $O(n \log n)$，故总复杂度为 $O(n \log n)$。

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll; // 本题中 a 的上线是 10 ^ 9，故答案可能会超过 int 的上限
const int N = 100005;
int n, a[N], diff[N], sz; // 离散化
// 树状数组
ll fw[N], res;
inline void add(int x, const ll c) {
    for (; x <= sz; x += x & -x) fw[x] = max(fw[x], c);
}
inline ll qry(int x) {
    ll res = 0;
    for (; x; x &= x - 1) res = max(res, fw[x]);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        diff[i - 1] = a[i];
    }
    sort(diff, diff + n);
    sz = unique(diff, diff + n) - diff;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(diff, diff + sz, a[i]) - diff + 1; // 求出离散化之后的值
        ll f = diff[a[i] - 1] + qry(a[i] - 1); // 求出 f[i]。
        res = max(res, f), add(a[i], f);       // 更新答案并将 f[i] 存到树状数组中 a[i] 的位置。
    }
    printf("%lld\n", res);
    return 0;
}