leetcode673-- Number of Longest Increasing Subsequence(注意这个题的思路)

# 小郑之家~

### 题目

 Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [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.



### 解答

class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 因为是求的最长的递增子序列的个数，将其记为res，并初始化为0,

# length[i] 表示以nums[i]为结尾的最长的递增子序列的长度
# cnt[i] 表示以nums[i]为结尾的具有length[i]那么长的递推子序列的个数

res = 0
maxLength = 0
length = [1]*len(nums)
cnt = [1]*len(nums)

for i in range(len(nums)):
for j in range(i):
if nums[j]>=nums[i]:
## 这时候直接pass
continue

# 下面都是在nums[j]<nums[i]的时候情况
if length[j]+1 == length[i]:
#说明
cnt[i] += cnt[j]  #刚开始cnt为1
elif(length[i]<length[j]+1):
# 说明还可以更长
length[i] = length[j]+1  #更新长度并直接将cnt换成j的
cnt[i] = cnt[j]
# 更新最大长度
maxLength = max(maxLength, length[i])

for i in range(len(nums)):
if maxLength == length[i]:
res += cnt[i]
return res