题目描述
blablabla
样例
blablabla
算法1
(线性dp) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int f[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>> a[i];
for(int i=1;i<=n;i++){//以i结尾的前i个数最长序列
f[i]=1;
for(int j=1;j<=i;j++){
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
}
int res = 0;
for(int i=1;i<=n;i++) res=max(res,f[i]);
cout<<res;
return 0;
}
算法2
(记忆化搜索) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int f[N];
int n;
int mem[N];
int dfs(int x){
if(x<0) return 0;
if(mem[x]) return mem[x];
int cnt = 0;
for(int i=1;i<x;i++){
if(a[i]<a[x]) cnt = max(cnt,dfs(i)+1);
}
mem[x] = cnt;
return cnt;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>> a[i];
/*for(int i=1;i<=n;i++){//以i结尾的前i个数最长序列
f[i]=1;
for(int j=1;j<=i;j++){
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
}*/
int res = 0;
for(int i=1;i<=n;i++) res = max(res,dfs(i)+1);
cout<<res;
/*int res = 0;
for(int i=1;i<=n;i++) res=max(res,f[i]);
cout<<res;*/
return 0;
}