Q673. Number of Longest Increasing Subsequence

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

 

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:

0 <= nums.length <= 2000
-106 <= nums[i] <= 106

For this question, my first thought is dynamic programming. Essentially, we want to maintain the solution to the following problem: the number of the longest subsequence of the prefix nums[1:k] which contains nums[k]. Also, we also want to keep the length of such longest subsequence.

The subproblem for nums[1:k] can be easily derived from all the previous subproblems (for smaller prefixes). Suppose for the subproblem, the number of longest subsequence is called n_ls and the length of such sequence is l_ls.

• If there exists nums[j] < nums[k] for any j < k, then find the j_max among the js' with longest length subsequence and update n_ls[k] = sum(n_ls[j_max]) and l_ls[k] = l_ls[j_max].
• If there is no such j, n_ls[k] = 1 and l_ls[k] = 1.

The Python submission is.

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # dp: dp[i] record the number of longest subsequences ends at i and the length of the subseq
        # dp[i] = sum(dp[k][0]),  for k such that k < i and nums[k] <= nums[i] and max k dp[k][1] if no k, then dp[i] = 1, 1
        # return sum(dp[k][0]) for max k of dp[k][1]  
        # complexity O(n^2)
        
        n = len(nums)
        if n <= 1:
            return n
        dp = [ [0, 0] for i in range(n) ]
        dp[0] = [1, 1]
        for i in range(1, n):
            max_l = 0
            good_k = []
            for j in range(i):
                if nums[j] < nums[i]:
                    if max_l < dp[j][1]:
                        good_k = [ j ]
                        max_l = max(max_l, dp[j][1])
                    elif max_l == dp[j][1]:
                        good_k.append(j)
            if len(good_k) == 0:
                dp[i] = [1, 1]
            else:
                dp[i][1] = max_l + 1
                for k in good_k:
                    dp[i][0] += dp[k][0]
        max_l = 0
        res = 0
        # print(dp)
        for k in range(n):
            if max_l < dp[k][1]:
                max_l = dp[k][1]
                res = dp[k][0]
            elif max_l == dp[k][1]:
                res += dp[k][0]
        return res

NOTE: We can easily see that the time complexity is $O(N^2)$ since we need to traverse all the previous subproblem in order to solve the current subproblem. From the solution in LC, it seems that we can also use segment tree to solve the problem which gives $O(N\log N)$ time complexity. But unfortunately, I’m not quite familiar with segment tree and I did not get the point. Now that I have to push segment tree to my wish list. As a starting point, I list some references: a leetcode discussion on segment tree, a good visualization tool for data structure and algorithm.
And I will solve Q307: Range Sum Query - Mutable in this post.