摘要
Title: 3662. 最大上升子序列和
Tag: dp、LIS、树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms

3662. 最大上升子序列和

题意

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

最朴素的树状数组可以求：
- 动态前缀最值问题
- 任意区间和问题
dp状态图

即 $f[i] = max(f[i], f[j] + a[i]), a[j] < a[i] && j < i$

由上图可见，需要 $O(n^2)$ 的复杂度，也就是和LIS类似
1
2
3
4
5
6
7
for i in range(1, n + 1):
for j in range(1, i + 1):
if a[i] > a[j]:
dp[i] = max(dp[i], dp[j] + a[i])

for i in range(1, n + 1):
res = max(res, dp[i])
可以发现，对于确定的i，决定其结果的是所有比a[i]小的a[j]值对应的最大的dp[j]
第二重循环，我们就可以用树状数组来优化，也就是动态求前缀最值
- 首先对输入的 $a$ 数组进行离散化，树状数组维护的是dp值，而我们离散化的是a数组
- 二分出离散化的下标x
- 然后，查询针对于tr数组的x下标之前的最大值，加上 a[i]，就是当前的dp值
- 其实也就间接保证了严格上升这一条件
  - 为什么呢？因为树状数组进行查询时，只查询tr数组中x下标之前的值，也就是说，不管先add还是后add，大于x下标的值当前是不考虑的，大于x下标这句话，对应到离散化数组中，就是大于a[i]的值，也就是我们一直只考虑小于等于a[i]的数对应的dp值
- 最后更新结果，并将当前的dp值放入树状数组

代码

'''
Author: NEFU AB-IN
Date: 2023-03-26 10:14:42
FilePath: \Acwing\3662\3662.py
LastEditTime: 2023-03-26 10:37:30
'''
# import
import sys
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e5 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

tr = [0] * N


def lowbit(x):
    return x & -x


def add(x, v):
    while x < N:
        tr[x] = max(tr[x], v)
        x += lowbit(x)


def query(x):
    res = 0
    while x:
        res = max(res, tr[x])
        x -= lowbit(x)
    return res


n, = read()
a = list(read())

xs = a[:]
xs = sorted(list(set(xs)))

res = 0
for i in range(n):
    k = bisect_left(xs, a[i]) + 1  # 保证下标大于0
    s = query(k - 1) + a[i]
    res = max(res, s)
    add(k, s)

print(res)

3662. 最大上升子序列和

题意

思路

代码