题目
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
Constraints:
1 <= nums.length <= 2000-106 <= nums[i] <= 106
思路
动态规划升级版。
代码
python版本：
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
dp = [[1, 1] for _ in range(len(nums))]
longest = 1
for i in range(len(nums)):
maxn = 1
count = 0
for j in range(i):
if nums[j] < nums[i]:
maxn = max(maxn, dp[j][0]+1)
for j in range(i):
if dp[j][0]+1 == maxn and nums[j] < nums[i]:
count += dp[j][1]
dp[i] = [maxn, max(count, dp[i][1])]
longest = max(longest, maxn)
return sum([i[1] for i in dp if i[0] == longest])
