题目描述: 最长上升子序列
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤1000
−1e9≤数列中的数≤1e9
输入样例
7
3 1 2 1 8 5 6
输出样例
4
基本思考框架
C++ 代码
这个写法时间复杂度是:n(状态数量)*n{状态计算) = O(N^2)
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int a[N];
int n;
int main()
{
cin>>n;
for(int i = 1 ; i <= n ;i++)
cin>>a[i];
int res = 0;
for(int i = 1 ; i <= n ;i ++ )
{ int tmp = 0;
for(int j = 1 ; j <= i ; j ++)
if(a[j]<a[i])
tmp = max(tmp,f[j]);
f[i] = tmp + 1;
res = max(res,f[i]);
}
cout<<res<<endl;
return 0;
}
Post modified: 2019-10-24