Number of Longest Increasing Subsequence LeetCode solution in Python

1
class Solution:
2
    def findNumberOfLIS(self, nums: List[int]) -> int:
3

4
        if not nums or len(nums) == 0:
5
            return 0
6

7
        def find_pos(sub, val):
8
            left, right = 0, len(sub) - 1
9
            while left < right:
10
                mid = (left + right) >> 1
11
                if sub[mid] >= val:
12
                    right = mid
13
                else:
14
                    left = mid + 1
15
            return left
16

17
        sub_list = []
18

19
        for val in nums:
20
            if len(sub_list) == 0 or val > sub_list[-1][-1][0]:
21
                # should append a new element at the end
22
                cur_count = (
23
                    sum([x[1] for x in sub_list[-1] if val > x[0]])
24
                    if len(sub_list) != 0
25
                    else 1
26
                )
27
                sub_list.append([(val, cur_count)])
28
            else:
29
                # get the last number to turn it back to a LIS problem
30
                cur_sub = [array[-1][0] for array in sub_list]
31
                pos = find_pos(cur_sub, val)
32
                # if pos == 0, means it is smallest, no need to look the previous level and set it to be 1
33
                cur_count = (
34
                    sum([x[1] for x in sub_list[pos - 1] if val > x[0]])
35
                    if pos > 0
36
                    else 1
37
                )
38
                sub_list[pos].append((val, cur_count))
39

40
        return sum([x[1] for x in sub_list[-1]])