Number of Longest Increasing Subsequence | Leetcode 673

Welcome to our deep dive on Number of Longest Increasing Subsequence (Leetcode 673). This is an excellent extension to the classic LIS problem that requires you to mentally juggle two distinct states simultaneously.

Problem Statement

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

Notice that the sequence has to be strictly increasing.

Example 1: 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: nums = [2,2,2,2,2] => Output: 5 (Explanation: The length of the longest continuous increasing subsequence is 1, and there are 5 subsequences' lengths equal to 1, so return 5.)

Approach: Double Dynamic Programming Arrays O(N^2)

In the standard LIS problem, we only care about finding the maximum sequence length ending at index i. However, here we also want to know how many ways we can reach that length!

We can solve this by maintaining two standard parallel DP arrays:

1. length[i]: The purely maximal length of an LIS ending strictly at index i.
2. count[i]: The exact physical number of distinct subsequences logically ending at index i that specifically achieve the maximal length[i].

For every number nums[i], we iterate through all previous numbers nums[j] where j < i. If nums[j] < nums[i], we can successfully append nums[i] to the subsequence ending at j.

• Case 1: We found a strictly longer sequence! If length[j] + 1 > length[i], we update length[i] = length[j] + 1, and we update count[i] = count[j].
• Case 2: We found another way to reach the current longest sequence length! If length[j] + 1 == length[i], we add count[j] to our current count[i]. count[i] += count[j].

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        
        n = len(nums)
        length = [1] * n
        count = [1] * n
        
        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]
                        
        max_len = max(length)
        res = 0
        for i in range(n):
            if length[i] == max_len:
                res += count[i]
                
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (673)