最长递增子序列
Longest Increasing Subsequence
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums，找到其中最长严格递增子序列的长度（子序列可以不连续，但需保持相对顺序）。
示例：nums = [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列为 [2, 3, 7, 101]，输出 4。
解题思路
- 基础 DP：dp[i] 为以 nums[i] 结尾的 LIS 长度，转移枚举所有更小值的前驱，O(n^2)。
- O(n log n) 解法用"贪心 + 二分"：维护数组 tails，tails[k] 为长度 k+1 的递增子序列的最小结尾值，它单调递增。
- 每个新元素二分查找它在 tails 中的位置：越界则 LIS 变长，否则替换该位置使结尾更小（更有利于后续扩展）。
- 注意 tails 不是任何一个具体的 LIS，只用于维护长度信息。
参考实现
查看参考实现Python · 建议先自行作答
import bisect
def lengthOfLIS(nums):
# tails[k]：长度为 k+1 的 LIS 的最小可能结尾值（单调递增）
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)