求最长递增子序列并输出序列

最长递增子序列（Longest Increasing Subsequence，LIS）是指在给定序列中，找到一个最长的单调递增的子序列。例如，在序列[2, 1, 5, 3, 6, 4, 8, 9, 7]中，最长的递增子序列为[1, 3, 4, 8, 9]，其长度为5。

在计算机科学和计算机应用的领域，求解最长递增子序列是一种非常常见的算法问题，对于排序、搜索、遗传学计算和其他相关领域都有广泛的应用。本文将从多个角度分析求解最长递增子序列的方法，并给出实现代码。

暴力求解

最朴素的方法是枚举所有可能的子序列，然后进行判断，选出其中满足单调递增条件的最长序列。这种方法的时间复杂度为O(2^n)，在数据规模较小时可以使用，但对于规模较大的序列来说，时间复杂度较高，不适合使用。

动态规划

动态规划（Dynamic Programming，DP）是最常用来求解LIS的算法。DP算法需要使用一个数组来记录每个位置的最长递增子序列长度，并根据前面位置的结果推导出后面位置的结果。具体步骤如下：

1. 初始化一个长度与序列相等的数组dp，dp[i]代表以第i个数为结尾的最长递增子序列长度。

2. 从第一个位置开始，依次求解每个位置的最长递增子序列长度。对于第i个位置，需要遍历前面的每个位置j(j

3. 遍历完整个序列后，dp数组中的最大值即为LIS的长度。

4. 利用dp数组中记录的信息，从后向前找到LIS中的每个元素，输出序列即可。

DP算法的时间复杂度为O(n^2)，适用于大多数数据规模。下面给出DP算法的实现代码。

```

def lis(nums):

n = len(nums)

dp = [1] * n

for i in range(1, n):

for j in range(i):

if nums[i] > nums[j]:

dp[i] = max(dp[i], dp[j] + 1)

max_len = max(dp)

res = []

for i in range(n - 1, -1, -1):

if dp[i] == max_len:

res.append(nums[i])

max_len -= 1

return res[::-1]

```

贪心+二分法

DP算法虽然简单易懂，但时间复杂度仍然较高。在实际应用中，我们可以通过一些优化算法来进一步提高效率。其中，贪心算法和二分法组合的方法被广泛应用。

具体步骤如下：

1. 维护一个数组d，数组中存储目前所得到的递增子序列，d[i]表示长度为i的递增子序列中末尾元素的最小值。

2. 遍历原始序列nums，如果当前数值大于d中的最大数，则将该数值添加到d的末尾。如果当前数值小于或等于d中的最大数，则在d中找到第一个大于等于该数值的元素，并将该元素替换为当前数值。

3. 遍历完整个序列后，d的长度即为LIS的长度。

4. 反向遍历d数组，依次输出递增子序列中的每个元素即为LIS的序列。

通过这种贪心算法和二分法的组合，可以将时间复杂度优化到O(n log n)级别，效率更高。下面给出实现代码。

```

import bisect

def lis(nums):

d = []

for num in nums:

pos = bisect.bisect_left(d, num)

if pos == len(d):

d.append(num)

else:

d[pos] = num

return d

```

总结

本文介绍了求解最长递增子序列的几种常用算法，并给出实现代码。暴力枚举虽然简单粗暴，但时间复杂度较高，不适用于大规模数据。动态规划算法是学习DP算法的入门必修课，时间复杂度为O(n^2)，可以满足大多数需求。贪心+二分法的组合是目前最优的LIS算法，时间复杂度为O(n log n)，效率更高。