题目描述
最长上升子序列
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
int a[N];
int f[N],g[N];
int n;
/*
f[i]:以a[i]为最高点 向前延伸的最长下降子序列的长度
g[i]:以a[i]为最高点 向后延申的最长下降子序列的长度
*/
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
memset(a,0,sizeof a);
memset(f,0,sizeof f);
memset(g,0,sizeof g);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
int res=-1;
for(int i=1;i<=n;i++) res=max(f[i],res);
for(int i=n;i>=1;i--){
g[i]=1;
for(int j=i+1;j<=n;j++) if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
res=max(res,g[i]);
}
cout<<res<<endl;
}
return 0;
}