题目链接:点击打开链接
正向求最长上升子序列并且将记录，反向求最长上升子序列并且维护答案。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
typedef long long ll;
int dp1[500005];
int dp2[500005];
int a[500005];
int tmp[500005];
int n ;
const int INF =1e9;
int ans;
void solve(){
fill(dp1,dp1+n,INF);
rep(i,0,n-1) {
*upper_bound(dp1,dp1+n,a[i])=a[i];
tmp[i]=lower_bound(dp1,dp1+n,INF)-dp1;
}
fill(dp2,dp2+n,INF);
for(int i=n-1;i>=0;i--){
*upper_bound(dp2,dp2+n,a[i])=a[i];
int k=lower_bound(dp2,dp2+n,INF)-dp2;
ans=max(ans,tmp[i]+k-1);
}
}
int main(){
cin>>n;
rep(i,0,n-1) scanf("%d",&a[i]);
solve();
cout<<ans<<endl;
return 0;
}
