1. LIS
题源：最长递增子序列
最长递增子序列有两种做法：O(n2)的动态规划和O(nlogn)的贪心+二分。
1.1 动态规划
定义dp[i]为以第i个元素为结尾的最长上升子序列长度，其中num[i]必须被选择，那么状态转移方程为(dp初始化值为1)：dp[i] = max(dp[j]) + 1; j < i, num[i] > num[j]
def findNumberOfLIS(nums): dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) 复制代码
复杂度分析：
- 时间复杂度: O(n2)
- 空间复杂度: O(n) dp[n]借助的空间
1.2 贪心 + 二分查找
我们要求得最长的上升子序列，那么我们应该保证序列上升的尽可能慢，因此每次添加到子序列后的数尽可能地小。 基于上面的想法，维护一个数组d[i]，表示长度为i的最长上升子序列，且d[i]为满足长度为i的上升子序列的最小值，使用len记录数组d的元素个数，初始值d[0] = num[0]。
算法流程：
- 遍历数组nums，当遍历到nums[i]时：
- 若nums[i] > d[len]，直接加入到数组末尾，len+1
- 否则，在d数组中寻找第一个大于nums[i]的位置，将其插入
- 以序列[0,2,5,3,7,101,18]
- 第一步插入0：d = [0]
- 第二步插入2：d = [0,2]
- 第三步插入5：d = [0,2,5]
- 第四步更新长度为3的最长子序列的末尾值：d = [0,2,3]
- 第五步插入7：d = [0,2,3,7]
- 第六步插入101：d = [0,2,3,7,101]
- 第四步更新长度为5的最长子序列的末尾值：d = [0,2,3,7,18]，得到最长递增子序列长度为5
def findNumberOfLIS(nums): d = [] for n in nums: if not d or n > d[-1]: d.append(n) else: left, right = 0, len(d) - 1 while left < right: mid = left + (right - left) // 2 if d[mid] < n: left = mid + 1 else: right = mid d[left] = n return len(d) 复制代码
复杂度分析：
- 时间复杂度: O(nlogn) 使用了二分查找
- 空间复杂度: O(n) d[n]借助的空间
2. 最长递增子序列的个数
2.1 动态规划
在LIS的基础上做进一步的求解：
定义dp[i]为以第i个元素为结尾的最长上升子序列长度，freq[i]为以第i个元素为结尾的最长上升子序列的个数。若nums的最长子序列长度为maxLen，那么答案为所有满足dp[i]=maxLen所对应的freq[i]之和。
dp[i] = max(dp[j]) + 1; j < i, num[i] > num[j]
freq[i]为所有满足dp[i]=dp[j] + 1的freq[j]之和
def findNumberOfLIS(nums): maxLen = 1 freq = [1] * len(nums) dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: if dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 freq[i] = freq[j] elif dp[j] + 1 == dp[i]: freq[i] += freq[j] maxLen = max(maxLen, dp[i]) sumFreq = 0 for i in range(nums): if dp[i] == maxLen: sumFreq += freq[i] return sumFreq 复制代码
复杂度分析：
- 时间复杂度: O(n2)
- 空间复杂度: O(n) dp[n]借助的空间
