673. Number of Longest Increasing Subsequence

class Solution:
    def findNumberOfLIS(self, A: List[int]) -> int:
        """ tc O(N^2) sc O(N)
        main idea: DP   
        1. create two dp array  cnt[i] : number of subsequence ending with i ;  LIS[i]:  max length of strictly increasing subsequence ending with i 
        2. loop through the whole array, and within the inner loop, find a element A[j] so that j < i and A[j] < A[i]
        3. check (1)if LIS[j] + 1 == LIS[i] => means  there are at least one subsequence ending with A[j] that can contribute to count for subsequence ending with A[i]     XXXXXj1 XXXj2XXi    
         (2) if LIS[j] + 1 > LIS[i]  means A[i] can be added directly into LIS for subsequence ending with A[j]       XXXXXXjXXXiXXX
        4.  check max LIS when inner loop ends  so we can find max LIS  
        5. loop all the dp array, accumulate all the count that LIS[i] == maxLIS  
        """
        n = len(A)
        LIS = [1] * n 
        cnt = [1] * n
        maxLen = 1
        for i in range(n):
            for j in range(i):
                if A[i] > A[j]:
                    if LIS[j] +1 == LIS[i] :
                        cnt[i] += cnt[j]
                        
                    elif LIS[j] + 1 > LIS[i]:
                        LIS[i] = LIS[j] + 1
                        cnt[i] = cnt[j]
                        
            maxLen = max(maxLen, LIS[i])
        
        res = 0
        for i in range(n):
            if LIS[i] == maxLen:
                res +=  cnt[i]
        return res 

class Solution:
    def findNumberOfLIS(self, A: List[int]) -> int:
        """" tc O(NlgN) sc O(N)
        main idea: use two binary searches to solve (1) position to insert the card (2) 
        1. for each number, find the insertion index in the LIS 
        2. count additional ways to be added once this number is inserted
        3. check if insertion point is at the end of LIS 
            (1) yes, directly add the number (negtive) as one deck into the decks; add history acuumutive ways onto paths 
            (2) no => append the number to the end of existing deck; overrite ends_deck at target index; append new ways to be added based on last card within same deck's acuumutive ways      
        """    
        decks, ends, ways = [],[], [] 
        for a in A:
            idx_deck = bisect.bisect_left(ends, a)
            
            # find additional ways it contributes to 
            number_ways = 1 
            if idx_deck > 0 :
                i_big = bisect.bisect(decks[idx_deck-1], -a)
                number_ways = ways[idx_deck-1][-1] - ways[idx_deck-1][i_big]
            
            if idx_deck == len(decks): # add new deck
                decks.append([-a])
                ends.append(a)
                ways.append([0,number_ways])
            
            else:
                decks[idx_deck].append(-a) # ascending order
                ends[idx_deck] = a 
                ways[idx_deck].append(ways[idx_deck][-1] + number_ways)
            
        return ways[-1][-1]