LeetCode 300. 最长上升子序列
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
1、题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例 1:
shell
输入：nums = [0,1,0,3,2,3]
输出：4
(最长的子序列为 [0,1,2,3])说明：
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
2、思路
解法 1
动态规划：
要求前 n 个元素的最长子序列，可以分解为求前 n-1 个元素的最长子序列，……依次类推，求前 2 个元素的最长子序列，先求前 1 个元素的最长子序列。
len_list[i] 列表存放前 i+1 个元素的最长子序列长度，采用两层循环实现，算法复杂度 O(n^2)。外层遍历 i，里层遍历更新 len_list[i]。
代码实现
python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 列表的长度
array_len = len(nums)
if array_len == 0:
return 0
# 初始化列表
len_list = [1] * array_len
# print(len_list)
# 存放子序列长度的最大值
subseq_len = 1
# 列表存放以第i个元素为起点的最长子序列的长度
for i in range(1, array_len):
for j in range(i):
if nums[j] < nums[i]:
len_list[i] = max(len_list[i], len_list[j] + 1)
subseq_len = max(len_list[i], subseq_len)
# print(i, len_list)
return subseq_len解法 2
解法 1 的过程实际上求出了所有的上升子序列的长度。为了优化时间复杂度，需要对这个解的动态规划过程进行剪枝。
在子序列长度相同时，最有“成长性”的上升子序列是结尾值最小的，即它最有可能变长。我们只需要记录这样的子序列即可。
用列表 seq_x 第 i 位表示长度为 i+1 的上升子序列中，末尾值最小的那一个值。
我们遍历输入的数组，取出一个数字 x：
- 如果
seq_x[i] < x <= seq_x[i+1]，则x可以加到seq_x[i]的后面，构成长度为i+2的上升子序列，且这个上升子序列的末尾值比seq_x[i+1]表示的子序列末尾值小，可以更新seq_x[i+1]的值为x。 - 如果
x比seq_x中所有数字都更大，则将x添加到seq_x的末尾，seq_x这个数组的长度+1。
最后，seq_x 的长度就是最长上升子序列的长度。
（关键点） 遍历数组的时间复杂度为 O(n)，而从上面的构造 seq_x 的过程可以看出，seq_x 的每个值必定比前一个值大，因此 seq_x 是有序的，所以我们的可以用二分查找法确定上述的 i 的值，查找过程的时间复杂度为 O(logn)。
因此整个算法的时间复杂度为 O(nlogn)。
代码实现
python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
"""
O(nlogn)的解法
"""
size = len(nums)
# 列表第i位表示长度为i+1的上升子序列中，末尾值最小的那一个值
seq_x = []
for i in range(size):
x = nums[i]
# 用二分查找法确定x在seq_x中的哪个位置，时间复杂度：O(logn)
i_low = 0
i_high = len(seq_x)
k = (i_low + i_high) // 2
while(i_low < i_high):
if seq_x[k] < x:
i_low = k + 1
else:
i_high = k
k = (i_low + i_high) // 2
if i_low == len(seq_x):
seq_x.append(x)
else:
seq_x[i_low] = x
return len(seq_x)