#LIS# [ssloj 1480].双端队列xLIS问题

Title

Solution

对于 $i$，我们可以求 $i$往后的最长上升子序列和最长下降子序列，比较 $l[i]+r[i]-1$得到最大值。
因为最长下降子序列可以放在双端队列的前面，与原来的最长上升子序列形成一个更长的子序列。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std; 
const int N=1e5+10; 
int n,a[N],c[N],d[N],len,l[N],r[N],ans=1; 
int main(){scanf("%d",&n); rep(i,1,n) scanf("%d",&a[i]); rep(i,1,n) c[i]=a[n-i+1]; len=0; rep(i,1,n) {int q=(lower_bound(d+1,d+len+1,c[i])-d); d[q]=c[i]; if (q==len+1) len++;r[i]=q; }memset(d,0,sizeof(d)); rep(i,1,n) c[i]=-a[n-i+1]; len=0; rep(i,1,n) {int q=(lower_bound(d+1,d+len+1,c[i])-d); d[q]=c[i]; if (q==len+1) len++;l[i]=q; }rep(i,1,n) ans=max(ans,l[i]+r[i]-1); printf("%d",ans); 
}