Number of Longest Increasing Subsequences

Patrick Leaton
Published: May 20, 2021, 2:41 a.m.
Problem 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 longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

 

Constraints:

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

 

The description was taken from https://leetcode.com/problems/number-of-longest-increasing-subsequence/.

Problem Solution

#O(N^2) Time, O(N) Space
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
       
        dp = [1]  * len(nums)
        counts = [1]  * len(nums)
 
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    if dp[i] <= dp[j]:
                        dp[i] = dp[j] + 1
                        counts[i] = counts[j]
                    elif dp[i] == dp[j] + 1:
                        counts[i] += counts[j]
       
        longest = max(dp)
        count = 0
        for i in range(0, len(dp)):
            if dp[i] == longest:
                count += counts[i]
        return count

Problem Explanation

If we are looking for a specific subsequence, not a sublist, that follows a specific constraint, that is typically an indication that Dynamic Programming can be applied.

That is how we will solve this problem.

More specifically, we can build an array that we will use as a lookup table.  We will split the input array into subproblems of length one, two, three, etc.  Within each subproblem, we will be asking "can we extend the length of an increasing subsequence up to this index?", if the answer is yes then we will increase the subsequence by the current index and repeat.

Where this question differs from Longest Increasing Subsequence, however, is we won't be returning the longest increasing subsequence, but the number of subsequences that share the length of the longest increasing subsequence.  For example, if we had two longest increasing subsequences of length four, we will be returning two and not four.

Other than that, the two solutions are very similar.

If the input array is empty then the longest increasing subsequence would be zero.

        if not nums:
            return 0

 

We will create our dp array where each index will hold the longest increasing subsequence up until that point.  The base case will be the value of one for each index because at minimum each value will be a subsequence of one, the element itself.

        dp = [1] * len(nums)

 

We will also create an array that stores the count of increasing subsequences with the same lengths. 

        counts = [1]  * len(nums)

 

We will then create our "expansion" loop, with the iterator i and this loop will traverse to the last index of the input array.  This is the loop that we will use to expand the range of our subproblem.

        for i in range(1, len(nums)):

 

Next, we will create our "subproblem partition" loop with the iterator j and this loop will only focus on the range between the index of the input array up to the index i is at.

              for j in range(0, i):

 

We will compare the elements at i and j.

If the element within the input array at i is less than or equal to the element at j then we don't have an increasing subsequence between the two elements, so we will just continue.

If that is not the case, we have an increasing subsequence at least between these two elements so we will ask our subproblem question, "should the index at i stay in the subsequence it is already in, or should it hop into the subsequence j is in, which would be the greatest number so far?".

If the element from the input array at index j is less than the element at index i, and the current subsequence length that i is in is less than or equal to the subsequence j is in, we'll have i jump into that subsequence because it is a net positive in both of those cases.  We will also copy the count over from j to i because since they are now in the same subsequence, they will share the same count.

                if nums[i] > nums[j]:
                    if dp[i] <= dp[j]:
                        dp[i] = dp[j] + 1
                        counts[i] = counts[j]
 

However, if the element from the input array at index j is less than the element at index i, and if we were to increment the subsequence j is in by one and it was to become the same length as the subsequence i is already in, then this isn't the first time we have counted a subsequence of this length.

If that is the case, then we will increment the count of i by the count of j to increment the count of this subsequence length.  

                    elif dp[i] == dp[j] + 1:
                        counts[i] += counts[j]

 

Once we are done with filling our dp array with each score of the longest increasing subsequence lengths, we will still need to count the occurrence of the longest increasing subsequence. 

Let's set the longest increasing subsequence length as a variable and also initialize a counter to zero.

        longest = max(dp)
        count = 0

 

We will traverse the dp array and each time we come across the length of the calculated longest increasing subsequence, we will increment our count by the number of subsequences we have saved in the counts array of the same index.

        for i in range(0, len(dp)):
            if dp[i] == longest:
                count += counts[i]

 

Once we have calculated the number of longest increasing subsequences, we will return the count.

        return count