Number of Longest Increasing Subsequences | Function to count the number of LIS in the array nums [ ] ; Base Case ; Initialize dp_l array with 1 s ; Initialize dp_c array with 1 s ; If current element is smaller ; Store the maximum element from dp_l ; Stores the count of LIS ; Traverse dp_l and dp_c simultaneously ; Update the count ; Return the count of LIS ; Given array arr [ ] ; Function Call
def findNumberOfLIS ( nums ) : NEW_LINE INDENT if not nums : NEW_LINE INDENT return 0 NEW_LINE DEDENT n = len ( nums ) NEW_LINE dp_l = [ 1 ] * n NEW_LINE dp_c = [ 1 ] * n NEW_LINE for i , num in enumerate ( nums ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if nums [ i ] <= nums [ j ] : NEW_LINE INDENT continue NEW_LINE DEDENT if dp_l [ j ] + 1 > dp_l [ i ] : NEW_LINE INDENT dp_l [ i ] = dp_l [ j ] + 1 NEW_LINE dp_c [ i ] = dp_c [ j ] NEW_LINE DEDENT elif dp_l [ j ] + 1 == dp_l [ i ] : NEW_LINE INDENT dp_c [ i ] += dp_c [ j ] NEW_LINE DEDENT DEDENT DEDENT max_length = max ( x for x in dp_l ) NEW_LINE count = 0 NEW_LINE for l , c in zip ( dp_l , dp_c ) : NEW_LINE INDENT if l == max_length : NEW_LINE INDENT count += c NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT arr = [ 1 , 3 , 5 , 4 , 7 ] NEW_LINE print ( findNumberOfLIS ( arr ) ) NEW_LINE