题目描述
该题 = ACWing 482合唱对形 (数据变了变)
C++ 代码
$O(nlogn)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1010 ;
int h[N];
int f[N],g[N],k[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
k[1]=h[1];
f[1]=1;
int l=1;
for(int i=2;i<=n;i++){ // f[i]:以i点结尾,区间[1,i],最长上升子序列 的长度
if(h[i]>k[l]) k[++l]=h[i],f[i]=l;
else {
int j=lower_bound(k+1,k+l+1,h[i])-k;
k[j]=h[i];
f[i]=j;
}
}
// 上面求出来 f[i],下面求 g[i]
memset(k,0,sizeof k);
g[n]=1;
l=1;
k[1]=h[n];
for(int i=n-1;i>=1;i--){ // g[i]:以i点结尾 , 区间[n,i] (n>=i),最长上升子序列 的长度
if(h[i]>k[l]) k[++l]=h[i],g[i]=l;
else{
int j=lower_bound(k+1,k+1+l,h[i])-k;
k[j]=h[i];
g[i]=j;
}
}
int res=-1;
for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1);
cout<<res;
return 0;
}