Question 673. Number of Longest Increasing Subsequence

Link

https://leetcode.com/problems/number-of-longest-increasing-subsequence/

My code:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0: return 0
        if len(nums) ==1: return 1
        #The list contains the maximum length end up with ith element in the nums
        ResultList = [[1,1]]
        #The dictionary provides the number of list given in the list
        for i in range(1,len(nums)):
            IndexList = []
            Length =1
            Num = 0
            for j in range(i):
                if nums[i]>nums[j]:
                    Length = max(Length,ResultList[j][0]+1)
                    IndexList.append(j)
            if Length != 1:
                for k in IndexList:
                    if ResultList[k][0] == Length -1:
                        Num += ResultList[k][1]
            if Num == 0:
                Num = 1
            ResultList.append([Length,Num])
        LengthList = [ResultList[i][0] for i in range(len(ResultList))]
        MaxLength = max(LengthList)
        Sum  = 0
        for s in range(len(ResultList)):
            if ResultList[s][0] == MaxLength:
                Sum += ResultList[s][1]
        return Sum

Explanation: There are two main problems in this question:1. How to determine the maximum length 2. How to count all the subsequence with maximum length. Here is the way I solve it. I construct a list L such that L[i] is a list that contains two elements. First element is the maximum length that ends up with element nums[i] and second element is the number of such subsequences. The recursion relation is as follows: for i+1 th element, we first check if it is larger than the chosen previous element. If so, then we know that the length of new List would be the maximum length of subsequence that ends up with chosen previous element plus one. Iterate through the beginning we may get the maximum length that ends up with i+1 th element. Second is to determine the number of the elements that ends up with i+1 th element and equals to the maximum length. So I do the iteration again to find total number. Notice that I initialise the length as 1 and Num as 0 because there is a situation that the i+1 th element might be smaller than all previous elements. In this situation , the maximum length would be one as itself. and the number would be 1 as just itself. Hence we iterate throught the nums list. Then we first find out the maximum length. Then we sum all the numbers that gives the maximum length. Then we return the result.