最长上升子序列
题目描述
这是一个简单的动规板子题。
给出一个由 \(n(n\le 5000)\) 个不超过 \(10^6\) 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
输入格式
第一行，一个整数 \(n\)，表示序列长度。
第二行有 \(n\) 个整数，表示这个序列。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
6
1 2 4 1 3 4
样例输出 #1
4
提示
分别取出 \(1\)、\(2\)、\(3\)、\(4\) 即可。
代码如下
using namespace std;
const int N=1e5+10;
int a[N];
int dp[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<=i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans;
return 0;
}