1. 题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
2. 示例
示例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
3. 题解
2种解题思路：动态规划、二分搜索
3.1 动态规划
动态规划的核心思想是数学归纳法
设计动态规划，首先需要一个dp数组，假设dp[0....i - 1]都已经算出来了，然后问自己，怎么通过这些结果算出dp[i]?
dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。那么以nums[i]结尾的最长递增子序列起码要包含它自己，即要找到前面序列结尾比nums[i]小的子序列，然后把nums[i]拼接上去，就形成了以nums[i]结尾的新的子序列，并在前面子序列的基础上加1。
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
最长子序列，只需要对dp数组遍历一次，取最大值即可。
for i in range(n):
res = max(res, dp[i])
3.2 二分搜索
二分搜索相对来说，难度大一些。以数组[10,9,2,5,3,7,101,18]为例，对其分堆。
首先10，对于第一个元素，单独为堆，此时堆数res = 1;
元素9，从0堆开始找，9小于10，放入0堆，res=1；
元素2，从0堆开始找，2小于9，放入0堆，res=1；
元素5，从0堆开始找，5大于2，此时只有堆0，那么需要再次创建一个堆来存放，res+=1，res=2；
元素3，从0堆开始找，3大于2，再找第1堆，3小于5，放入，res=2；
元素7，7大于2，7大于3，创建新堆，第2堆堆顶元素为7，res=3；
元素101，大于0，1，2堆顶元素，创建新堆，res=4；
元素18，大于0,1,2堆顶元素，放入第3堆，res=4；
输出结果：4（堆的个数就是最长子序列的长度，因为在后面堆里面一定能找到小于等于前面元素）。
4. Code实现
4.1 动态规划
1 class Solution: 2 # 动态规划 3 def lengthOfLIS(self, nums: List[int]) -> int: 4 if len(nums) <= 1: 5 return len(nums) 6 n = len(nums) 7 dp, res = [1 for _ in range(n)], 0 8 for i in range(n): 9 for j in range(0, i): 10 if nums[i] > nums[j]: 11 dp[i] = max(dp[i], dp[j] + 1) 12 res = max(res, dp[i]) 13 return res
4.2 二分搜索
1 class Solution: 2 # 二分搜索 3 def lengthOfLISB(self, nums: List[int]) -> int: 4 n = len(nums) 5 if n < 2: 6 return n 7 top = [0 for _ in range(n)] 8 # 堆数 9 res = 0 10 for i in range(n): 11 # 要处理的牌 12 cur = nums[i] 13 # 搜索左边界的二分搜索 14 left, right = 0, res 15 while left < right: 16 mid = (left + right) // 2 17 if top[mid] > cur: 18 right = mid 19 elif top[mid] < cur: 20 left = mid + 1 21 else: 22 right = mid 23 # 没找到合适的堆，新建一堆 24 if left == res: 25 res += 1 26 top[left] = cur 27 return res
5. 结语
努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！
如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。