题目描述
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
复制 输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2:
复制 输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
解题思路
动态规划
以[300][中等][贪心][二分][动态规划][树状数组] 最长上升子序列 为基础, 对于位置i,我们不仅要维护以nums[i]结尾的最长递增序列的长度length[i], 还要知道改最长序列所有可能的数量count[i].
对于i后的位置j, 如果有nums[i] < nums[j], 则nums[j]可以组成新的上升序列. 还是从0到j - 1遍历所有位置, 判断nums[j]是否更大. length[j]的取其中的最大, count[j]则记录这个最大值对应的可能组合的累计, 如果遍历过程中遇到了更长的上升子序列, 更新length[j]的同时, count[j]重置为对应的产生更大序列的count[i], 重新计数.
复制 class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
length = [1] * n
count = [1] * n
for j in range(n):
for i in range(j):
if nums[j] > nums[i]:
if length[i] >= length[j]:
length[j] = length[i] + 1
count[j] = count[i]
elif length[i] + 1 == length[j]:
count[j] += count[i]
max_len = max(length)
return sum([count[i] for i, t_len in enumerate(length) if t_len == max_len]) 贪心 + 二分
[300][中等][贪心][二分][动态规划][树状数组] 最长上升子序列 中的贪心+二分 方法, 使用一个长度为最终最长递增子序列长度的数组, 记录了每个长度对应的所有递增子序列中, 末尾数字的最小值 . 本题中, 还是使用这种套路, 但记录的内容更复杂了. 详情参考上面的题解答案.
复制 class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
length = []
count = []
for num in nums:
index1 = bisect.bisect_left([t[0] for t in length], num)
if index1 == len(length):
if len(length) == 0:
length.append([num])
count.append([1])
else:
last_length = length[-1]
last_count = count[-1]
index2 = bisect.bisect_left(last_length, num)
length.append([num])
count.append([last_count[0] - (last_count[index2] if index2 < len(last_count) else 0)])
else:
if index1 == 0:
length0 = length[0]
count0 = count[0]
length0.insert(0, num)
count0.insert(0, len(length0))
else:
t_length = length[index1 - 1]
t_count = count[index1 - 1]
index2 = bisect.bisect_left(t_length, num)
t1 = t_count[0] - (t_count[index2] if index2 < len(t_count) else 0)
length[index1].insert(0, num)
count[index1].insert(0, t1 + count[index1][0])
return count[-1][0]