一、题目
1、原题链接
3662. 最大上升子序列和
2、题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an。
请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。
请问这个 最大值是多少？
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出最大的上升子序列和。
数据范围
对于前三个测试点，1≤n≤4。
对于全部测试点，1≤n≤105,1≤ai≤109。
输入样例1：
2
100 40
输出样例1：
100
输入样例2：
4
1 9 7 10
输出样例2：
20
1
样例解释*
对于样例 1，我们只选取 100。
对于样例 2，我们选取 1,9,10。
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）dp[i]表示所有以a[i]结尾的的所有上升子序列中序列和的最大值。
以a[i]前面的一个数为是原序列第几个元素（或者没有）对dp[i]进行分类。
设a[i]前面一个数为a[k](k>=1&&k<i&&a[k]<a[i])，由于最后一个数固定是a[i]，所以我们要求该子序列和的最大值，只要保证前面以a[k]结尾的子序列的和最大即可。即转移方程为 dp[i]=max(dp[i],dp[k]+a[i])
（2）如果不进行dp优化，时间复杂度最坏为O(n2)，会超时。所以需要利用离散化先将序列中的数映射到一个数组中去，这样就转化成了求所有小于a[i]的所有前缀的最大值，利用树状数组进行优化，最终将时间复杂度控制在O(nlogn)。
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
LL tr[N]; //树状数组
int a[N],q[N]; //q[]为离散化数组
int n,m;
//返回最低位的一位1
int lowbit(int x){
return x&-x;
}
//添加、更新tr[]，存储以x结尾的子序列最大和
void add(int x,LL v){
for(int i=x;i<=m;i+=lowbit(i)){
tr[i]=max(tr[i],v);
}
}
//查询1~x的前缀的最大值
LL query(int x){
LL ans=0;
for(int i=x;i;i-=lowbit(i)){
ans=max(ans,tr[i]);
}
return ans;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
//离散化
memcpy(q,a,sizeof a);
sort(q,q+n);
m=unique(q,q+n)-q;
LL ans=0;
for(int i=0;i<n;i++){
int x=lower_bound(q,q+m,a[i])-q+1; //二分离散化后的值
LL sum=query(x-1)+a[i];
ans=max(ans,sum);
add(x,sum);
}
cout<<ans;
return 0;
}
三、知识风暴
树状数组
