标题: 最长上升子序列 II [打印本页] 作者: 我爱普洱茶 时间: 2023-4-4 14:32 标题: 最长上升子序列 II 最长上升子序列 II
题目描述
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1 ≤ N ≤100000
-10^9 ≤ 数列中的数 ≤ 10^9
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
算法1
(DP) O(n^2)
动态规划状态转移
时间复杂度
O(n^2)，数据范围10^5会TLE
空间复杂度
dont know
C++ 代码
[code]#includeusing namespace std;const int N = 1010;int n;int a[N];int f[N];int main(){ cin >> n; for(int i = 1; i a; int len = 0; for(int i = 0; i < n; i ++) { int l = 0, r = len; while(l < r) { int mid = l + r + 1 >> 1; if(q[mid] < a) l = mid; else r = mid - 1; } len = max(len, r + 1); q[r + 1] = a; } cout