Leetcode 673 Number of Longest Increasing Subsequence

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

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].

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.

• This question can be solved by Dynamic Programming. It is similar with question 300. Longest Increasing Subsequence. But now, the question is asking how many numbers of the longest increasing subsequence.

• I personally think this question should belong to hard level.

• To get the answer, we need to build connection between length of the longest increasing subsequence and the count the of length. For that, we need to get current element’s length of longest increasing subsequence and meanwhile we also need to know the current element’s count of longest increasing subsequence. It’s bit of tricky here, think twice. The answer is sum up each longest increasing subsequence’s count.

• Find the base case: We need two dp list here, one is for the length of the longest increaseing subsequence and each element represent the current longest length. Another one is for counting the number of such sequence and each element represent the count of increasing of include element. length and count are at least 1 unless there is no input length = [1]n count = [1]n

• Find the pattern: The length is easy to come up. If the current element is greater than before (make the subsequence increasing), then we will get the max length of previous plus 1. Else just stay in 1(Not increasing).

• The count is hard to understand. The current element is the sum of previous longest increasing subsequence whose max element is less than current element(this will make the current subsequence keep increasing and also means the previous longest increasing subsequences’ length is 1 less than the current longest increasing subsequence)

• Create dp list will cost O(2n) and iterate the dp will cost ((n-1)*n) in total will be O((n-1)*n+2n)

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        if N <= 1: return N
        lengths = [1] * N #lengths[i] = longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for i, num in enumerate(nums):
            for j in range(i):
                if nums[j] < nums[i]:
                    if lengths[j] >= lengths[i]:
                        lengths[i] = max(lengths[i],lengths[j]+1)
                        counts[i] = counts[j]
                    elif lengths[i]==lengths[j] + 1:
                        counts[i] += counts[j]
        longest = max(lengths)
        return sum(c for j, c in enumerate(counts) if lengths[j] == longest)