Number of Longest Increasing Subsequences — DP + BIT

Problem

Return the count of all longest increasing subsequences.

Approach — DP O(n²)

dp[i] = (length, count) of LIS ending at i. For each j < i with nums[j] < nums[i]:

If dp[j].len + 1 > dp[i].len: update length and count
If equal: add counts

Time: O(n²) | Space: O(n)

Solutions

Python — O(n²) DP

class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        n=len(nums)
        dp=[(1,1)]*n
        for i in range(1,n):
            for j in range(i):
                if nums[j]<nums[i]:
                    ll,lc=dp[j]; il,ic=dp[i]
                    if ll+1>il: dp[i]=(ll+1,lc)
                    elif ll+1==il: dp[i]=(il,ic+lc)
        max_len=max(l for l,_ in dp)
        return sum(c for l,c in dp if l==max_len)

Complexity

O(n²): DP | O(n log n): Segment tree on coordinate-compressed values