Skip to content

673. Number of Longest Increasing Subsequence

Difficulty Topics

Description

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 the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

 

Constraints:

  • 1 <= nums.length <= 2000
  • -106 <= nums[i] <= 106

Solution

number-of-longest-increasing-subsequence.py
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        length = [1] * n
        count = [1] * n
        m = 1

        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] += count[j]

            m = max(m, length[i])

        return sum(count[i] for i, l in enumerate(length) if l == m)