python一本通1097题目答案

题目描述：

给定一个长度为n的整数序列a，求它的最长上升子序列的长度。

输入格式：

第一行包含整数n。

第二行包含n个整数，表示整数序列a。

输出格式：

输出一个整数，表示最长上升子序列的长度。

数据范围：

1≤n≤1000，
−109≤a[i]≤109

样例：

输入：
7
3 1 2 1 8 5 6
输出：
4

算法1

(暴力枚举) $O(n^2)$

暴力枚举所有的子序列，判断是否是上升子序列，并记录最长的长度。

时间复杂度

暴力枚举所有的子序列，时间复杂度为O(n^2)。

Python 代码

n = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(n):
for j in range(i, n):
if all(a[k] < a[k+1] for k in range(i, j)):
ans = max(ans, j-i+1)

print(ans)

算法2

(动态规划) $O(n^2)$

用dp[i]表示以a[i]为结尾的最长上升子序列的长度，对于每个a[i]，遍历之前的a[j]，如果a[j] < a[i]，则dp[i] = max(dp[i], dp[j]+1)。

时间复杂度

遍历数组需要O(n)的时间，遍历之前的数组需要O(n)的时间，因此总时间复杂度为O(n^2)。

Python 代码

n = int(input())
a = list(map(int, input().split()))

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

print(max(dp))

算法3

(贪心+二分查找) $O(nlogn)$

定义一个数组d，d[i]表示长度为i的最长子序列的末尾元素的最小值。遍历数组a，对于每个a[i]，如果a[i]大于d[len]，则把a[i]加入d[len+1]，否则在d中二分查找第一个大于等于a[i]的位置，并替换为a[i]。最后d中元素个数即为最长上升子序列的长度。

时间复杂度

遍历数组需要O(n)的时间，二分查找需要O(logn)的时间，因此总时间复杂度为O(nlogn)。

Python 代码

n = int(input())
a = list(map(int, input().split()))

d = [a[0]]
for i in range(1, n):
if a[i] > d[-1]:
d.append(a[i])
else:
l, r = 0, len(d)-1
while l < r:
mid = (l+r) // 2
if d[mid] < a[i]:
l = mid+1
else:
r = mid
d[l] = a[i]

print(len(d))