「每日一题」第14天——300. 最长上升子序列
300. 最长上升子序列
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/难度：中等
题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(nlogn) 吗?
思路
这道题也是动态规划的思路。
我们先定义状态，使用数组dp保存每步子问题的最优解。
dp[i] 代表从头元素开始，到第i个元素(包含i)的最长上升子序列的长度。
状态转移方程：
for i:0 -> n-1:dp[i] = Max{dp[j]}+1 j:0->i-1&&a[j]<a[i]
伪代码：
for i: 0->n-1:for j: 0->i-1:dp[i]
这里两层循环，时间复杂度为O(n^2)，空间复杂度O(n)
但是题目中有个进阶，要求我们找出O(nlogn)的时间复杂度的算法。
我们可以想想，在这里的伪代码：
for i: 0->n-1:for j: 0->i-1: 我们这第二层循环加速dp[i]
为什么我们可以在第二层循环加速，那是因为第一层遍历我们不能省略，只能在第二层想办法。
我们拿题目中的数组来举例子：[10,9,2,5,3,7,101,18]
如果我们维护一个数组L，进来一个新的元素，如果比较最后的元素大，那就加入数组，如果比最后元素小，那就替换。
[10] [10,9,2,5,3,7,101,18][9] [9,2,5,3,7,101,18][2] [5,3,7,101,18][2,5] [3,7,101,18][2,3] [7,101,18] 3和5比较，使用二分查找插入到5前面并替换5[2,3,7] [101,18][2,3,7,101] [18][2,3,7,18] [] 长度为4，这里有多种子序列，长度是一样的
这里使用了二分查找，第二层循环时间复杂度为O(logn)，总体时间复杂度为O(nlogn)。
代码见方案代码。
方案代码
动态规划:
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if nums == []:return 0dp = [1]for i in range(1,len(nums)):dp.append(1)for j in range(i):if(nums[j] < nums[i]):dp[i] = max(dp[i], dp[j]+1)return max(dp)
二分查找：
import bisectclass Solution:def lengthOfLIS(self, nums: List[int]) -> int:res = []for i in range(len(nums)):p = bisect.bisect_left(res,nums[i])if p == len(res):res.append(nums[i])else:res[p]=nums[i]return len(res)
往期回顾：
「每日一题」第13天——169. 多数元素
「每日一题」第12天——1071. 字符串的最大公因子
「每日一题」第11天——1013. 将数组分成和相等的三个部分
「每日一题」第10天——543. 二叉树的直径