题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N] , a[N];
int n;
int main()
{
cin >>n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) // 枚举分别从1到n个对应的a[i]的值 做结尾
{
f[i] = 1; // 以i结尾的子序列只有i自己 故先将f[i]设为1
for(int j = 1; j < i; j++) // 枚举i前的数
{
if(a[j] < a[i]) f[i] = max(f[i] , f[j] + 1); // 若i前的数小于 a[i] 则看一下以这个数结尾的子序列的长度+1(a[i]这个数)的长度 与
// 以a[i]结尾的子序列的长度谁大
}
}
int res = 0;
for(int i = 1; i <= n; i++)
{
res = max(res , f[i]); // 计算以不同的数结尾的子序列的长度谁的最大
}
cout << res << endl;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla