题目描述
给定一个长度为 N 的整数序列 a1,a2,…,aN。
请你计算该序列的最长上升子序列的长度。
上升子序列是指数值严格单调递增的子序列。
输入格式
第一行包含整数 N。
第二行包含 N 个整数 a1,a2,…,aN。
输出格式
一行,一个整数,表示最长上升子序列的长度。
数据范围
1≤N≤1000,
0≤ai≤10000。
样例
输入样例:
7
1 7 3 5 9 4 8
输出样例:
4
算法思想:
求1 7 3 5 9 4 8的最长上升子序列
定义f[i]表示前i个数,在a[N]中以a[i]为结尾的最长上升子序列的长度
例:
1 f[1] = 1
1 7 f[2] = max(f[2],f[1]+1) = 2
1 7 3 f[3] = max(f[3],f[1]+1) = 2
1 7 3 5 f[4] = max(f[4],f[3]+1) = 3
1 7 3 5 9 f[5] = max(f[5],f[4]+1) = 4
1 7 3 5 9 4 f[6] = max(f[6],f[3]+1) = 3
1 7 3 5 9 4 8 f[7] = max(f[7],f[5]+1) = 4
求n个数的最长上升子序列,可以求前n-1个数的最长上升子序列,再跟第n个数进行判断
C++ 代码
//求最长上升子序列
#include <iostream>
using namespace std;
const int N = 10010;
int n;
int a[N],f[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
f[i] = 1;
for(int j=0;j<=n;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]);
}
printf("%d",res);
return 0;
}