Python 中最长递增子序列问题（LIS）的解决方法

1. 动态规划
   最长递增子序列（Longest Increasing Subsequence, 简称 LIS）是典型的动态规划问题。可以使用动态规划来解决。具体思路如下：

设 $dp[i]$ 表示以第 $i$ 个元素为结尾的最长递增子序列的长度。则有以下状态转移方程：

$$dp[i]=max{dp[j]+1} \quad (0 \leq j<i,a_j<a_i)$$

其中 $j$ 是 $i$ 之前的任意一个下标，只要 $a_j<a_i$ 即可。

最终的 LIS 长度为 $\max_{0\leq i< n}dp[i]$。

代码示例：

def LIS(a):
n = len(a)
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)
return max(dp)

a = [1, 5, 3, 4, 6, 9, 7, 8]
print(LIS(a)) # 输出 6，即 [1, 3, 4, 6, 9, 8]

2. 贪心算法+二分查找
   除了动态规划，还有一种时间复杂度更低的解决方法，那就是贪心算法+二分查找。具体思路如下：

定义一个辅助数组 $d$，对于任意的 $0 \leq i \leq len(a)$，$d[i]$ 表示长度为 $i+1$ 的所有递增子序列的最后一个元素中最小的那个。

具体来说，对于 $a$ 中的每一个元素 $x$，进行如下操作：

1). 如果 $x$ 大于 $d$ 数组中的最后一个元素，那么就追加到 $d$ 数组最后。

2). 否则，就在 $d$ 数组中找到第一个大于等于 $x$ 的元素，并用 $x$ 替换它。

最终 $d$ 数组的长度即为 LIS 的长度。

代码示例：

def LIS(a):
d = []
for x in a:
if not d or x > d[-1]:
d.append(x)
else:
l, r = 0, len(d) - 1
while l < r:
mid = (l + r) // 2
if d[mid] >= x:
r = mid
else:
l = mid + 1
d[l] = x
return len(d)

a = [1, 5, 3, 4, 6, 9, 7, 8]
print(LIS(a)) # 输出 6，即 [1, 3, 4, 6, 9, 8]