Solutions CS101

Appearance

02757: 最长上升子序列 ​

dp, binary search, http://cs101.openjudge.cn/practice/02757

一个数的序列b~i~，当b~1~ < b~2~ < ... < b~S~的时候，我们称这个序列是上升的。对于给定的一个序列(a~1~, a~2~, ..., a~N~)，我们可以得到一些上升的子序列(a~i1~, a~i2~, ..., a~iK~)，这里1 ≤  i~1~ < i~2~ < ... < i~K~ ≤  N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 ≤  N ≤  1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4

来源：翻译自 Northeastern Europe 2002, Far-Eastern Subregion 的比赛试题

2020fall-cs101，王君宇。思路：和最大上升子序列和类似，都是需要双重循环的 dp，外循环确定每个元素 dp初始值为 1，内循环遍历小数进行转移方程。

python
input()
b = [int(x) for x in input().split()]

n = len(b)
dp = [1]*n

for i in range(n):
    for j in range(i):
        if b[j]<b[i]:
            dp[i] = max(dp[j]+1, dp[i])
    
print(max(dp))

2020fall-cs101，李博海

python
import bisect
n = int(input())
l = [int(x) for x in input().split()]
dp = [1e9]*n
for i in l:
    dp[bisect.bisect_left(dp, i)] = i
print(bisect.bisect_left(dp, 1e8))

2020fall-cs101，章斯岚。这里用i+1是为了防止a[0:i]可能是空列表导致runtime error。

与 OJ3532最大上升子序列和，一样，i改为1即可。

python
dp = [0]*(10000+2)
input()
for i in map(int, input().split()):
    dp[i+1] = max(dp[0:i+1]) + 1
print(max(dp))