题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法 1
(动态规划) $O(n)$
状态表示:$f[i]$,表示以 arr[i] 结尾的最大上升子序列的长度。
状态计算:$f[i] = max(f[i], f[j] + 1), j \in [0, i - 1]$
边界:
- 初始化:
f[i] = 1
, 表示以当前数结尾的最长上升子序列的长度为 $1$ -
答案:
- 所有
f[i]
的最大值就是最长上升子序列的长度 $cnt$ - 需要输出最长上升子序列,则从后往前寻找,如果当前位置的 f[i] == cnt (长度),则将其加入到答案中(从后往前放到答案中),并将 cnt –
- 所有
时间复杂度
$O(n^2)$
空间复杂度
$O(n)$
class Solution {
public:
vector<int> LIS(vector<int>& arr) {
int n = arr.size();
vector<int> f(n);
int cnt = 0;
for (int i = 0; i < n; i ++ ) {
f[i] = 1;
for (int j = 0; j < i; j ++ ) {
if (arr[i] > arr[j])
f[i] = max(f[i], f[j] + 1);
}
cnt = max(cnt, f[i]);
}
// 从后往前找,找到的就是字典序最小的序列
vector<int> res(cnt);
for (int i = n - 1, j = cnt; j > 0; i -- ) {
if (f[i] == j)
res[ -- j] = arr[i];
}
return res;
}
};
算法 2
(贪心 + 二分) $O(n)$
参考题解: https://www.acwing.com/solution/content/2192/
f[i]
用来存储长度为 $i + 1$ 的最长上升子序列结尾的最小值,可证明 $f$ 是单调递增的,即对于长度为 $x$ 的最长上升子序列的结尾最小值 $w$ 和 长度为 $y$ 的最长上升子序列的结尾最小值 $v$,如果 x < y
则必然存在 w < v
。证明见
g[i]
用于存储以当前数 a[i]
结尾的最长上升子序列的长度。
cnt
:表示最长上升子序列的长度,初始值为 $0$
算法步骤:
始终要记得 $f$ 数组和 $g$ 数组的含义
-
初始化
f[cnt ++ ](f[0]) = a[0], g[0] = 1
-
下标从 $1$ 开始遍历数组 $a$
- 如果当前数大于目前上升子序列结尾的最小值即
a[i] > f[cnt - 1]
时,直接把a[i]
加入到 $f$ 数组中,长度 + 1(cnt + 1),并作为当前最长上升子序列新的结尾,同时更新g[i] = cnt
。 - 否则
a[i] <= f[cnt - 1]
,此时需要从 $f$ 数组中找到第一个大于等于a[i]
的数,假设它的下标为 $k$,那么以下标 $k$ 结尾的最长上升子序列的长度为 $k + 1$,更新长度为 $k + 1$ 的最长上升子序列的结尾最小值为a[i]
。
由于 $f$ 数组是单调的,所以可以使用二分在 $O(long)$ 的时间内找到 $k$ 然后更新最小值,即f[k] = a[i]
,同时更新g[i] = k + 1
;
- 如果当前数大于目前上升子序列结尾的最小值即
-
最后要输出序列,只需从后往前扫描 $g$ 数组,如果
g[i] == cnt
则将其加入到答案中,且cnt --
。
时间复杂度
$O(nlogn)$
空间复杂度
$O(n)$
class Solution {
public:
vector<int> LIS(vector<int>& a) {
int n = a.size();
int cnt = 0;
vector<int> f(n), g(n);
f[cnt ++ ] = a[0], g[0] = 1;
for (int i = 1; i < n; i ++ ) {
if (a[i] > f[cnt - 1]) f[cnt ++ ] = a[i], g[i] = cnt;
else {
int l = 0, r = cnt - 1;
while (l < r) {
int mid = l + r >> 1;
if (f[mid] >= a[i]) r = mid;
else l = mid + 1;
}
f[l] = a[i];
g[i] = l + 1;
}
}
// cout << cnt << endl;
// for (int i = n - 1; i >= 0; i -- ) cout << g[i] << " ";
vector<int> res(cnt);
for (int i = n - 1; i >= 0; i -- ) {
if (g[i] == cnt)
res[ -- cnt] = a[i];
}
return res;
}
};
谢谢大佬
加油~
大佬, 你大几呀
研二
大佬,我问一下,为什么这么做一定能保证长度最长啊
我好像理解了,因为是子序列,打扰了大佬
加油~
冲冲冲~