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

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

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦