896. 最长上升子序列 II
摘要
Title: 896. 最长上升子序列 II
Tag: 贪心、二分、LIS模型
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
896. 最长上升子序列 II
-
题意
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
-
思路
贪心考虑，就像单调栈一样，一直维护一个递增的序列，只不过在来了一个比较小的数时，需要用它替代数组中对应的数
比如 1 3 7 8，比如这个数是4，那么就可以通过二分，将序列更改为 1 3 4 8
比如
可以看出，栈中的队列不一定是真实存在的，这种方法求出来的只有栈的size是有效的 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34'''
Author: NEFU AB-IN
Date: 2022-03-07 14:42:36
FilePath: \ACM\Acwing\896.py
LastEditTime: 2022-03-07 15:03:36
'''
N = int(1e5 + 10)
a = [0] * N
dp = []
def find(x):
l, r = 0, len(dp) #当列表一开始没有值时，将右边界设为 len(dp)，不减1，防止越界
while l < r:
mid = l + r >> 1
if dp[mid] >= x:
r = mid
else:
l = mid + 1
return r
n = int(input())
a[1:] = list(map(int, input().split()))
for i in range(1, n + 1):
# pos = bisect_left(dp, a[i])
pos = find(a[i])
if pos == len(dp):
dp.append(a[i])
else:
dp[pos] = a[i]
print(len(dp))
