300. 最长递增子序列
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1提示：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
解答
思路：子集型回溯
有选或不选以及枚举选哪个两种思路。
- 选或不选：为了比较大小，需要知道上一个所选的数字，两个参数
- 枚举选哪个：枚举到
num[i]时，只需要比较它和前面数字的大小，所有比它小的都可以成为候选
我们以 枚举选哪个 为例子：
- 当前操作：枚举
nums[j]，其中j < i and nums[j] < nums[i] - 当前问题：以
nums[i]结尾的 最长递增子序列 Longest Increasing Subsequence，LIS 长度 - 它的子问题：以
nums[j]结尾的 LIS 长度
递归关系式：
注意枚举选哪个这种情况下，dfs(0)..dfs(n - 1) 都可能是答案，也就是以 nums[i] 结尾的 LIS 取最大值。
这里有
- 时间复杂度为
- 空间复杂度为
代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dfs(i):
res = 0
for j in range(i):
if nums[j] < nums[i]:
res = max(res, dfs(j))
return res + 1
ans = 0
for i in range(n):
ans = max(ans, dfs(i))
return ans # max(dfs(i) for i in range(n))思路：递推
二重循环：
- 时间复杂度为
- 空间复杂度为
代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j])
f[i] += 1
return max(f)思路：参考 LCS
nums 的 LIS 等价于 nums 和 排序去重后 的 nums 的 LCS。这是因为 LIS 一定是 排序去重后 的 nums 的一个子序列，它同时也是 nums 的一个子序列，因此它们的 LCS 一定是 LIS。
可惜这种做法也是
代码
class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
n = len(s)
m = len(t)
f = [0] * (m + 1)
for x in s:
pre = f[0]
for j, y in enumerate(t):
tmp = f[j + 1] # 上一轮的 f[i][j]
if x == y:
f[j + 1] = pre + 1
else:
f[j + 1] = max(f[j + 1], f[j])
pre = tmp
return f[m]
def lengthOfLIS(self, nums: List[int]) -> int:
nums_sort = sorted(set(nums))
return self.longestCommonSubsequence(nums, nums_sort)思路：优化时间复杂度
动态规划想要优化时间复杂度，有个技巧就是：交换状态和状态值。
f[i]表示 末尾元素 为nums[i]的 LIS 长度g[i]表示 长度 为i + 1的 IS 的 末尾元素 的最小值（它足够小才能方便扩展）
nums
= [1, 6, 7, 2, 4, 5, 3]
g = [1]
g = [1, 6]
g = [1, 6, 7]
g = [1, 2, 7] # 长度为 2 的 IS 为 1, 2
g = [1, 2, 4] # 长度为 3 的 IS 为 1, 2, 4
g = [1, 2, 4, 5]
g = [1, 2, 3, 5] # 长度为 3 的 IS 为 1, 2, 3这种由于没有重叠子问题，只是不断通过新的 nums[i] 来更新 g 数组，因此不是动态规划，而是一个贪心问题。
我们接下来证明 g 数组的一些性质：
g是 严格递增 的- 每一次只能更新一个位置
- 更新的位置是 第一个
>= nums[i]的数的下标
如果 g 不是严格递增的，那么存在 g[i] >= g[j], i < j，那么 g[j] 所对应的 IS 中的第 < g[j] <= g[i]，而这与 g[i] 的定义矛盾。
假设一次更新了两个位置，说明 nums[i] 导致 g 中的两个位置变成了 nums[i]，而这与严格递增是矛盾的，因此每一次只能通过 nums[i] 更新 g 中的一个位置。
同时由于我们是从左到右遍历的，因此 nums[i] 一定可以和 g 中的数构成 IS，也就是一定会被添加进去。添加的位置只需要遍历 g（可以二分），找到 第一个 >= nums[i] 的数：
- 对于更大的数：不能替换，否则违背严格递增
- 对于更小的数：不能替换，否则违背末尾元素最小的要求
- 因此只能是第一个满足
>= nums[i]的数
由于 g 恰好递增，因此可以使用二分查找第一个 >= nums[i] 的数的下标 j，如果 j 不存在，那么把 nums[i] 直接添加到 g 的末尾，否则修改 g[j] = nums[i]。
一次遍历，每次都需要
- 时间复杂度为
- 空间复杂度为
代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
g = []
for x in nums:
j = bisect_left(g, x)
if j == len(g):
g.append(x)
else:
g[j] = x
return len(g)进一步，可以把 nums 当作 g 数组（滚动变化），此时空间复杂度为
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
ng = 0 # 表示 g 数组的长度
for x in nums:
j = bisect_left(nums, x, 0, ng) # nums[0:ng] = g[:]
if j == ng:
nums[ng] = x
ng += 1
else:
nums[j] = x
return ngbisect_left(nums, x, 0, 0) == 0，二分零区间的结果为 0。
变形：非严格递增
如果允许 LIS 中有相同元素，即非严格递增，那么 g 也是一个非严格递增序列（用小于的反证法证明）。这个时候，和 nums[i] 相同的 g[j] 就不用修改了，修改的是第一个 > nums[i] 的 g[j]。
nums
= [1, 6, 7, 2, 2, 5, 2]
g = [1]
g = [1, 6]
g = [1, 6, 7]
g = [1, 2, 7]
g = [1, 2, 2]
g = [1, 2, 2, 5]
g = [1, 2, 2, 2]代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
ng = 0 # 表示 g 数组的长度
for x in nums:
j = bisect_right(nums, x, 0, ng) # nums[0:ng] = g[:]
if j == ng:
nums[ng] = x
ng += 1
else:
nums[j] = x
return ng