C++(clang++11) 解法, 执行用时: 71ms, 内存消耗: 4224K, 提交时间: 2021-01-30 20:49:42

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=2e5+10;
int n,m;
int a[maxn];
ll f[maxn];
ll tr[maxn];
void add(int x,ll k)
{
	while(x<=2e5)
	{
		tr[x]=max(tr[x],k);
		x+=x&-x;
	}
 }
ll dor(int x)
{
	ll ret=0;
	while(x)
	{
		ret=max(ret,tr[x]);
		x-=x&-x;
	}
	return ret;
}
int main()
{
    
    
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	ll ans=0;
	for(int i=n;i>=1;i--)
	{
		f[i]=a[i];
		f[i]=max(f[i],a[i]+dor(a[i]));
		add(a[i],f[i]);
		ans=max(f[i],ans);
	}
	cout<<ans<<endl;
	return 0;
}