Longest Increasing Subsequence
你会得到一个整数列表 nums。子序列保留其中一些元素，并保持它们原来的顺序，丢弃其余元素；保留的元素不必彼此相邻。返回值从左到右严格递增的最长子序列的长度。连续两个相等的值不算递增。
函数
- numsinteger-array
- 可供选择的整数列表
- 返回值integer
- 最长严格递增子序列的长度
约束条件
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
示例
- 输入
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- 输出
- 4
- 解释
- 1、2、5、9 是递增的，1、2、5、7 和 1、2、4、7 也都是递增的：长度为 4。没有任何由 5 个值组成的序列能保持递增。
- 输入
- nums = [7, 7, 7, 7]
- 输出
- 1
- 解释
- 这些值必须严格递增，因此两个 7 不能出现在同一个子序列中。单个元素本身也算一个子序列，所以答案是 1。
- 输入
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- 输出
- 4
- 解释
- -4、0、3、16 的长度为 4。从第一个元素 12 开始，只能得到两个值，例如 12、25：最长子序列不一定要从开头开始。
进阶
你能否在返回最长递增子序列本身及其长度的同时，仍以 O(n log n) 的时间运行？
提示
逐个打开提示，每个都会多透露一点。
整个列表中最佳的子序列很难直接描述。针对每个索引
i，提出一个更具体的问题：以nums[i]结尾的最长递增子序列是什么？以
nums[i]结尾的子序列，要么只有nums[i]，要么接在某个更早的nums[j] < nums[i]结尾的最长子序列后面。选出这样的j中最优的一个，然后加 1。答案是这些值中的最大值，无论它在哪里结束。要将复杂度降到
O(n²)以下，需要为每种长度保留该长度的子序列可能具有的最小末尾值。这些值始终有序，因此可以用二分查找判断新数字是能延长最长子序列，还是替换某个末尾值。
题解
包含 n 个数字的列表有 2^n 个子序列，数量太多，无法逐一检查。对于每个索引，询问以该位置恰好结尾的最长递增子序列有多长，可以得到一个 O(n²) 的表。最快的方法是对每种长度，记录该长度的子序列可能以哪个最小值结尾，并通过二分查找为每个元素找到位置。
获取或跳过每个元素
结果正确，但无法在最大的测试中运行完毕
思路
对每个元素，决定是否保留它；只有当 nums[i] 大于上一个保留的值时，才能保留它。longest(i, prev) 表示从索引 i 开始还能添加的最多元素数，此时上一个保留的元素位于 prev（或 -1）。跳过当前元素会得到 longest(i+1, prev)；保留当前元素会得到 1 + longest(i+1, i)。每个递增子序列都是由这些选择构成的一条路径。
对于 1、2、3、……、n，每个分支都会继续展开，每增加一个元素，调用次数就会翻倍：2^40 已经约等于 10^12。不过，(i, prev) 这样的不同组合最多只有 n² 个。
算法
- 编写
longest(i, prev)，其中prev是上一个保留元素的索引，或者是-1。 - 如果
i超出末尾，返回 0。 - 跳过
nums[i]：best = longest(i+1, prev)。 - 如果
prev是-1，或者nums[i] > nums[prev]，就保留它：best = max(best, 1 + longest(i+1, i))。 - 返回
best。答案是longest(0, -1)。
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)以每个索引结尾的最长子序列
思路
令 ending[i] 表示最后一个元素为 nums[i] 的最长递增子序列的长度。nums[i] 前面的元素（如果存在）是某个满足 j < i 且 nums[j] < nums[i] 的 nums[j]，并且以它结尾的部分应尽可能长。因此，对这些 j，ending[i] = 1 + max(ending[j])；如果没有这样的 j，则为 1。从左到右填表。
对于 [3, 1, 8, 2, 5, 9, 4, 7]，表为 [1, 1, 2, 2, 3, 4, 3, 4]：5 可以接在 3、1 或 2 后面，其中最长的子序列长度为 2，所以 ending[4] = 3。答案是最大的表项，因为最佳子序列可以在任意位置结束。
n(n-1)/2 次比较：当 n = 2500 时，约为 3.1 × 10^6 次。
算法
- 创建
ending，并将每个条目都设为 1。 - 从左到右遍历每个
i，查看所有j < i。 - 如果
nums[j] < nums[i]，并且ending[j] + 1更大，就将ending[i]设为ending[j] + 1。 - 返回
ending中的最大值。
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)使用二分查找找到最小的尾部值
思路
对于每种长度，只保留该长度递增子序列可能以最小值结尾的那个值：长度为 k+1 时，记为 tails[k]。结尾越小越好：能接在 9 后面的值，也能接在 5 后面。tails 始终严格递增：去掉长度为 k+2 的递增子序列的最后一个值，就会得到一个长度为 k+1、结尾更小的递增子序列。
对于每个 x，二分查找第一个 ≥ x 的结尾值。如果找不到，就追加 x：它能延长最长的递增子序列。否则，用 x 替换该结尾值：短一位的子序列以小于 x 的值结尾，因此 x 能得到相同长度且结尾更小的子序列。
例如 1，tails 依次变为 [3]、[1]、[1, 8]、[1, 2]、[1, 2, 5]、[1, 2, 5, 9]、[1, 2, 4, 9]、[1, 2, 4, 7]：长度为 4。在 [1, 2, 4, 9] 中，4 出现在 9 之后，因此只有 tails 的长度有意义。
算法
- 从空列表
tails开始。 - 对于
nums中的每个x，使用二分查找找到第一个满足tails[k] ≥ x的索引k。 - 如果没有尾值满足
≥ x，就追加x。 - 否则，将
tails[k] = x。 - 返回
tails的长度。
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
易错点和边界情况
- 返回
ending[n-1]，而不是最大的条目。对于[1, 2, 3, 0]，最后一个条目是 1，但答案是 3。 - 使用
≤而不是<进行比较。[7, 7, 7, 7]必须返回 1，而不是 4。 - 在 tails 版本中，搜索第一个
> x的尾值，而不是第一个≥ x的尾值。这样，第二个 7 会追加在第一个 7 之后，把相等的值也算作递增。 - 误用了连续版本。在示例 1 中，最长的相邻递增序列是 2、5、9（长度为 3），而答案是 4。
- 在 Lua 或 R 中保留从 0 开始的索引，但数组的索引从 1 开始。
prev = -1标记应改为 0，二分查找的索引范围应为 1 到当前大小。
常见问题3
最长递增子序列的时间复杂度是多少？
tails 方法的时间复杂度为 O(n log n)，空间复杂度为 O(n)：每个元素进行一次二分查找。遍历每一对索引的表需要 O(n²) 时间，而尝试每个子序列需要 O(2ⁿ) 时间。
最长递增子序列中的耐心排序是什么？
它是一个以纸牌游戏命名的 tails 方法。每个尾部都是一堆牌最上面的牌：一张牌会放到最左边那堆顶部牌的值大于或等于它的牌堆上，否则就开始新的一堆。牌堆的数量就是答案。
那要如何找到最长非递减子序列呢？
允许相等的相邻元素。在表格中，使用 nums[j] ≤ nums[i]。在 tails 方法中，搜索第一个严格大于 x 的尾值，这样相等的值会扩展列表，而不是替换尾值。这样，[7, 7, 7, 7] 会返回 4。
def lengthOfLIS(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 8, 2, 5, 9, 4, 7]
预期输出
4