|
给定一个未排序的整数数组，找到最长递增子序列的个数。
列：
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
# 解析：完全遍历，内圈比较，在比较长度的同时对其数量进行存储。
class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums) # 数组长度
if size <= 1: return size # 0,1特殊情况
dp = [1] * size # 初始化每一位对应的最长序列值
count = [1] * size # 初始化每一位对应的最长序列值的数目
maxCount = 0 # 最长序列
for i in range(1, size): # 外圈遍历
for j in range(i): # 内圈遍历
if nums[i] > nums[j]: # 大于时才存在递增，才能进入判断
if dp[j] + 1 >dp[i]: # 若j的序列长度+1较大
dp[i] = dp[j] +1 # 那么更新i的dp序列长度
count[i] = count[j] # 并且将i处的数目换成j处的数目，因为我们要的是最长序列值的数目
elif dp[j] + 1 == dp[i]: # 如果相等
count[i] += count[j] # 那么同为最大序列，将count值相加即可
if dp[i] > maxCount: # 找出i处的最长序列后与maxCount作比较
maxCount = dp[i] # maxCount始终存储最大的序列长度
res = 0 # 初始化结果
for i in range(size): # 对序列长度进行遍历
if maxCount == dp[i]: # 找出最长序列长度相同且都为最长的下标
res += count[i] # 然后将他们对应的数目全部加起来
return res # 返回结果
|