【ACWing】3662. 最大上升子序列和

https://www.acwing.com/problem/content/description/3665/

给定一个长度为 n n n的整数序列 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1​,a2​,…,an​。请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。请问这个最大值是多少？

输入格式：
第一行包含整数 n n n。
第二行包含 n n n个整数 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1​,a2​,…,an​。

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

数据范围：
对于前三个测试点， 1 ≤ n ≤ 4 1≤n≤4 1≤n≤4。
对于全部测试点， 1 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 9 1≤n≤10^5,1≤a_i≤10^9 1≤n≤105,1≤ai​≤109。

设 f [ i ] f[i] f[i]是以 a i a_i ai​为结尾的和最大的严格上升子序列的和，那么这样的子序列可能有两种情况，其一是只含 a i a_i ai​，此时最大和就是 a i a_i ai​；另一种是除了 a i a_i ai​还含前面的数，此时最大和是 a i + max ⁡ j < i ∧ a [ j ] < a [ i ] f [ j ] a_i+max_{j

#include 
#include 
#include 
using namespace std;

const int N = 1e5 + 10;
int n, a[N];
long tr[N];
vector xs;
long f[N];

int get(int x) {
  return lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
}

int lowbit(int x) {
  return x & -x;
}

void add(int x, long v) {
  for (int i = x; i <= n; i += lowbit(i))
    tr[i] = max(tr[i], v);
}

long query(int x) {
  long res = 0;
  for (int i = x; i; i -= lowbit(i))
    res = max(res, tr[i]);
  
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    xs.push_back(a[i]);
  }

  // 离散化
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  long res = 0;
  for (int i = 1; i <= n; i++) {
    int k = get(a[i]);
    // 求小于a[i]的f的最大值
    f[i] = query(k - 1) + a[i];
    res = max(res, f[i]);
    add(k, f[i]);
  }

  printf("%ldn", res);
}

时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间 O ( n ) O(n) O(n)。