BEADSNB - Beads
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#define MAX 100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
int a[MAX];
int ci[MAX];
int cd[MAX];
int fi[MAX];
int fd[MAX];
int n;
void maximize(int &x,const int &y) {
if (x<y) x=y;
}
void init(void) {
scanf("%d",&n);
FORD(i,n,1) scanf("%d",&a[i]);
}
void LIS(void) {
int sz=1;
fi[1]=1;
ci[1]=1;
FOR(i,2,n) {
if (a[i]<=a[ci[1]]) {
fi[i]=1;
ci[1]=i;
continue;
}
if (a[i]>a[ci[sz]]) {
sz++;
fi[i]=sz;
ci[sz]=i;
continue;
}
int l=1;
int r=sz;
int m;
while (true) {
if (l==r) {
m=r;
break;
}
if (r-l==1) {
if (a[i]>a[ci[r]]) m=r;
else m=l;
break;
}
m=(l+r)/2;
if (a[i]>a[ci[m]]) l=m;
else r=m-1;
}
fi[i]=m+1;
if (a[ci[m+1]]>a[i]) ci[m+1]=i;
}
}
void LDS(void) {
int sz=1;
fd[1]=1;
cd[1]=1;
FOR(i,2,n) {
if (a[i]>=a[cd[1]]) {
fd[i]=1;
cd[1]=i;
continue;
}
if (a[i]<a[cd[sz]]) {
sz++;
fd[i]=sz;
cd[sz]=i;
continue;
}
int l=1;
int r=sz;
int m;
while (true) {
if (l==r) {
m=r;
break;
}
if (r-l==1) {
if (a[i]<a[cd[r]]) m=r;
else m=l;
break;
}
m=(l+r)/2;
if (a[i]<a[cd[m]]) l=m;
else r=m-1;
}
fd[i]=m+1;
if (a[cd[m+1]]<a[i]) cd[m+1]=i;
}
}
void answer(void) {
int res=0;
FOR(i,1,n) maximize(res,fi[i]+fd[i]-1);
printf("%d",res);
}
int main(void) {
//freopen("BEADS.INP","r",stdin);
//freopen("BEADS.OUT","w",stdout);
init();
LIS();
LDS();
answer();
return 0;
}