AcWing 895. 最长上升子序列
原题链接
简单
作者:
gkb
,
2024-04-11 19:50:19
,
所有人可见
,
阅读 1
记忆化搜索
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int n,arr[N];
int mem[N];
//所有以第u个数为结尾的上升子序列的长度
//子问题是u前面的并且比u小的那个数为结尾的上升子序列的长度
//u前面的并且比u小的那个数可能与u相邻,也可能压根没这个数
int dfs(int u)
{
if(mem[u]) return mem[u];
int ans=1;
for(int i=u-1;i>=1;i--)
{
if(arr[i]<arr[u]) ans=max(ans,dfs(i)+1);
}
mem[u]=ans;
return mem[u];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
int res = 0;
//每个数都要当一次u,我们不知道哪个u构成的上升子序列最大
for (int i = 1; i <=n; i++)
{
res = max(res, dfs(i));
}
cout<<res<<endl;
return 0;
}