难度: Medium
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 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。
提示:
1 <= nums.length <= 2000-106 <= nums[i] <= 106运行时间: 54 ms
内存: 16.6 MB
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
# if not nums: return 0
# dq = list()
# totals = list()
# for num in nums:
# index = len(dq)-1
# if not dq or num > dq[-1]:
# dq.append(num)
# totals.append(defaultdict(int))
# else:
# while index >= 0 and dq[index] >= num:
# index -= 1
# dq[index+1] = num
# if not index+1:
# totals[index+1][num] +=1
# else:
# totals[index+1][num] += sum([val for key,val in totals[index].items() if key < num])
# return sum(totals[-1].values())
dp, count = [], []
for num in nums:
l, r = 0, len(dp)
while l < r:
mid = (l + r) >> 1
if dp[mid][-1] >= num:
r = mid
else:
l = mid + 1
i = l
c = 1
if i > 0:
# 找d[i-1]中结尾小于num的数量
l, r = 0, len(dp[i - 1])
while l < r:
mid = (l + r) >> 1
if dp[i-1][mid] < num:
r = mid
else:
l = mid + 1
k = l
c = count[i-1][-1] - count[i-1][k]
if i == len(dp):
dp.append([num])
count.append([0, c])
else:
dp[i].append(num)
count[i].append(c + count[i][-1])
return count[-1][-1]
该题解使用动态规划来解决最长递增子序列的个数问题。具体思路如下： 1. 使用两个列表dp和count来记录状态。其中dp[i]表示长度为i+1的递增子序列的结尾元素列表，count[i]表示以dp[i]中每个元素结尾的递增子序列个数累计值列表。 2. 遍历给定数组nums中的每个元素num： a. 二分查找dp中第一个大于等于num的元素位置i。 b. 如果i等于dp的长度，说明num可以接在当前最长递增子序列之后，形成一个新的最长子序列，因此将num添加到dp中，并在count中记录以num结尾的子序列个数为1。 c. 如果i小于dp的长度，说明num可以替换dp[i]中的元素，形成一个新的长度为i+1的递增子序列。此时在dp[i]中二分查找第一个大于num的元素位置k，然后将num添加到dp[i]的末尾，并在count[i]中累加count[i-1][-1] - count[i-1][k]，表示以num结尾的递增子序列个数。 3. 最终返回count[-1][-1]，即以dp中最后一个元素结尾的递增子序列总数。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
dp, count = [], []
for num in nums:
# 二分查找dp中第一个大于等于num的元素位置i
l, r = 0, len(dp)
while l < r:
mid = (l + r) >> 1
if dp[mid][-1] >= num:
r = mid
else:
l = mid + 1
i = l
c = 1
if i > 0:
# 二分查找dp[i-1]中第一个大于num的元素位置k
l, r = 0, len(dp[i - 1])
while l < r:
mid = (l + r) >> 1
if dp[i-1][mid] < num:
r = mid
else:
l = mid + 1
k = l
# 累加以num结尾的递增子序列个数
c = count[i-1][-1] - count[i-1][k]
if i == len(dp):
# num可以接在当前最长递增子序列之后，形成新的最长子序列
dp.append([num])
count.append([0, c])
else:
# num可以替换dp[i]中的元素，形成新的长度为i+1的递增子序列
dp[i].append(num)
count[i].append(c + count[i][-1])
return count[-1][-1]
在算法中，数组dp用于存储每个长度序列的可能结尾元素，从而追踪每种长度的递增子序列可能的结尾值。具体来说，dp[i]是一个列表，记录所有可能作为长度为i+1的递增子序列的结尾的元素。而数组count则用来记录与dp对应的递增子序列的数量。count[i]也是一个列表，与dp[i]中的每个元素对应，记录以该元素结尾的长度为i+1的递增子序列的数量。这样的设计使得算法能够在更新新的序列结尾元素时，同时更新对应的递增子序列数量，便于计算总的递增子序列个数。
通过二分查找在dp中寻找第一个大于等于num的元素位置的目的是确定num可以插入或替换的位置，以维持每个长度的递增子序列的最小可能结尾。这种方法确保了递增子序列尽可能地小且长，因为替换成一个更小或相等的元素可以延长后续可能的递增子序列。这是因为一个小的元素更有可能被后续的更大数值接上，从而形成更长的递增子序列。
表达式`count[i-1][-1] - count[i-1][k]`用于计算新元素num在长度为i+1的递增子序列中的出现次数。这里，`count[i-1][-1]`表示所有长度为i的递增子序列的总数，而`count[i-1][k]`表示以小于num的元素结尾的长度为i的递增子序列的总数。因此，这个表达式的结果是以大于或等于num的元素结尾的长度为i的递增子序列的总数，即num可以在这些子序列后接续形成新的递增子序列的数量。
当nums数组中存在重复元素时，算法通过在dp中寻找第一个大于等于num的元素位置来处理重复。如果找到的位置i小于dp的长度，即dp[i]中已有元素大于等于num，算法会将num添加到dp[i]中，这样做不会影响已有的递增子序列的任何其他结尾，保证了递增子序列的正确性和完整性。如果num正好等于某一位置的元素，它将替换现有的那个元素，而不会增加新的序列，仅仅是提供了一个新的可能的结尾，而不改变序列的总数。