LC 0673 [M] Number of Longest Increasing Subsequence - ALawliet/algorithms GitHub Wiki

Intuition
To find the frequency of the longest increasing sequence, we need
First, know how long is the longest increasing sequence
Second, count the frequency
Thus, we create 2 lists with length n
dp[i]: meaning length of longest increasing sequence
cnt[i]: meaning frequency of longest increasing sequence
If dp[i] < dp[j] + 1 meaning we found a longer sequence and dp[i] need to be updated, then cnt[i] need to be updated to cnt[j]
If dp[i] == dp[j] + 1 meaning dp[j] + 1 is one way to reach longest increasing sequence to i, so simple increment by cnt[j] like this cnt[i] = cnt[i] + cnt[j]
Finally, sum up cnt of all longest increase sequence will be the solution
This is a pretty standard DP question. Just like most sequence type of DP question, we need to loop over each element and check all previous stored information to update current.
Time complexity is O(n*n)

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        m = 0
        dp = [1] * n
        cnt = [1] * n
        
        for r in range(n):
            for l in range(r):
                if nums[l] < nums[r]:
                    
                    if dp[r] < dp[l] + 1:
                        dp[r] = dp[l] + 1
                        cnt[r] = cnt[l]
                        
                    elif dp[r] == dp[l] + 1:
                        cnt[r] += cnt[l]
                        
            m = max(m, dp[r])                        
        return sum(c for l, c in zip(dp, cnt) if l == m)

class Solution:
    def findNumberOfLIS(self, nums):
        # dp solution, 2 arrays
        # length[i] stores the longest length ending at nums[i]
        # count[i] counts the number of paths with length length[i]

        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[i] > nums[j]:
                    # length[i] = max(length[j]+1, length[i]) 
                    # but we need to compute count also
                    if length[i] == length[j]:
                        length[i] = length[j]+1
                        count[i]  = count[j]
                    elif length[i] == length[j]+1:
                        count[i] += count[j]

        maxLength = max(length)
        return sum([count[i] for i in range(n) if length[i] == maxLength])