（以下题解根据我自己在评论区的回答修改而成，并且添加了“二分查找 + 贪心算法”的思路。）
首先仔细审题，明确题目中的条件。
1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；
2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列，因为 3 重复了，所以不是“严格上升”的；
一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 。
这个问题具有最优子结构，因此可以考虑使用动态规划完成。
动态规划
定义状态：dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。注意：以第 i 个数字为结尾，即要求 nums[i] 必须被选取。反正一个子序列一定会以一个数字结尾，那我就将状态这么定义，这一点是常见的。
状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍，如果当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了， dp[i] 的值就是它们的最大值加 。即比当前数要小的那些里头，找最大的，然后加
。
状态转移方程：dp(i) = max( 1 + dp(j) if j < i and dp[i] > dp[j])。
最后不要忘了，扫描一遍这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。
Python 代码：
class Solution:
# 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
# 那么题目要求的，就是这个 dp 数组中的最大者
# 以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例
# dp 的值： 1 1 1 2 2 3 4 4
def lengthOfLIS(self, nums):
size = len(nums)
# 特判
if size <= 1:
return size
dp = [1] * size
for i in range(1, size):
for j in range(i):
if nums[i] > nums[j]:
# + 1 的位置不要加错了
dp[i] = max(dp[i], dp[j] + 1)
# 最后要全部一看遍，取最大值
return max(dp)
二分查找 + 贪心算法
每一次来一个新的数 num，就找 tail 数组中大于等于 num 的那个数，试图让它变小，以致于新来的数有更多的可能性接在它后面，成为一个更长的“上升子序列”，这是“贪心算法”的思想。
Python 代码：
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return size
tail = []
for num in nums:
# 找到大于等于 num 的第 1 个数
l = 0
r = len(tail)
while l < r:
mid = l + (r - l) // 2
if tail[mid] < num:
l = mid + 1
else:
r = mid
if l == len(tail):
tail.append(num)
else:
tail[l] = num
return len(tail)
（本题完）
