Number of Longest Increasing Subsequence

Intuition

Solution

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        dp = []
        for i in range(len(nums)):
            length, count = 1, 1
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j][0] >= length:
                        length = dp[j][0] + 1
                        count = dp[j][1]
                    elif dp[j][0] == length - 1:
                        count += dp[j][1]
            dp.append([length, count])

        m, v = 1, 0
        for l, c in dp:
            if l > m:
                m = l
                v = c
            elif l == m:
                v += c
        return v