题目描述
有一串数字,求这串数字的严格上升子序列长度的最大值。
算法1
(线性dp)
状态表示 f[i]
- 集合 长度为i的上升子序列的末尾元素的值
- 属性 min
状态计算
- 方程
- 当a[i] > f[ed]时 f[ed ++ ] = a[i]
- 当a[i] <= f[ed] 时 二分找到第一个大于等于a[i]的f[k] f[k] = a[i]
时间复杂度
外层循环n次,内层每次转移时间为O(logn)
故时间复杂度为O(nlogn)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define f(i, j, k) for(int i = j; i <= k; i ++ )
int n, f[N], ed = 0;
signed main()
{
cin >> n;
f(i, 1, n)
{
int a;
cin >> a;
if(!ed || a > f[ed - 1]) f[ed ++ ] = a;
else f[lower_bound(f, f + ed, a) - f] = a;
}
cout << ed << endl;
}