给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式第一行包含整数 N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围1≤N≤1000,
−1e9≤数列中的数≤1e9
输入样例
7
3 1 2 1 8 5 6
输出样例
4
线性dp
这题的状态表示可以用一维的来做,状态表示中的集合是什么呢?我一开始想的是前i个中的上升子序列的集合,此时包不包含i都行,但是后来发现在状态计算的时候不好划分,如果按照包不包含i来划分的话,包含的情况下你不知道这个i是不是比前面的某个子序列的最大的数大。所以这里我们的状态表示是一定是包含i的,也就是以i结尾的最长子序列的集合,然后我们求这些里面的最大值就可以划分成以i - 1结尾和i结尾。最后算完之后只需要遍历一遍f数组,找出里面以某个结尾的最长子序列的最大值就是本题所找的答案。
状态转移方程为 f[i] = max(f[k] + 1)
这个k是从1到i - 1中以k结尾的最长子序列,找到其中能包含i的最大值。也就是a[k] < a[i]时的最大值。
时间复杂度
O(n^2)
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int k = 1; k < i; k ++ )
if (a[k] < a[i]) f[i] = max(f[i], f[k] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res, f[i]);
cout << res;
return 0;
}
当中有一步每次循环i的时候会把f[i]重置成1,这是因为以i为结尾的最长子序列最小是只含有i这一个数的情况下,所以要有个初始状态保证计算正确。