Given an unsorted array of integers, find the number of longest increasing subsequence.


Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].



Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.



Note:
Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Difficulty: interview

Starter code:

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

Solutions:
def bs(arr, val, key=lambda x:x):
     l, r = 0, len(arr)-1
     if key(arr[l])>val:
         return l
     if key(arr[r])<=val:
         return r+1
     while l+1<r:
         m = (l+r)>>1
         v = key(arr[m])
         if v<=val:
             l = m
         else:
             r = m
     return r
 
 def bs_left(arr, val, key=lambda x:x):
     l, r = 0, len(arr)-1
     if key(arr[l])>=val:
         return l
     if key(arr[r])<val:
         return r+1
     while l+1<r:
         m = (l+r)>>1
         v = key(arr[m])
         if v<val:
             l = m
         else:
             r = m
     return r
             
 
 class Solution:
     def findNumberOfLIS(self, nums):
         if not nums: return 0
         N = len(nums)
         l, dp = 0, [[] for _ in range(N)]
         for n in nums:
             idx1 = bs_left(dp, n, lambda _:_[-1][0] if _ else sys.maxsize)
             if idx1==l:
                 l += 1
             if idx1==0:
                 dp[0].append([n, (dp[0][-1][1] if dp[0] else 0)+1])
             else:
                 idx2 = bs(dp[idx1-1], -n, lambda _:-_[0])
                 dp[idx1].append([n, (dp[idx1][-1][1] if dp[idx1] else 0)+(dp[idx1-1][-1][1] if idx2==0 else (dp[idx1-1][-1][1]-dp[idx1-1][idx2-1][1]))])
         return dp[l-1][-1][1]

def bs(arr, val, key=lambda x:x):
     l, r = 0, len(arr)-1
     if key(arr[l])>val:
         return l
     if key(arr[r])<=val:
         return r+1
     while l+1<r:
         m = (l+r)>>1
         v = key(arr[m])
         if v<=val:
             l = m
         else:
             r = m
     return r
 
 def bs_left(arr, val, key=lambda x:x):
     l, r = 0, len(arr)-1
     if key(arr[l])>=val:
         return l
     if key(arr[r])<val:
         return r+1
     while l+1<r:
         m = (l+r)>>1
         v = key(arr[m])
         if v<val:
             l = m
         else:
             r = m
     return r
             
 
 class Solution:
     def findNumberOfLIS(self, nums):
         if not nums: return 0
         N = len(nums)
         l, dp = 0, [[] for _ in range(N)]
         for n in nums:
             idx1 = bs_left(dp, n, lambda _:_[-1][0] if _ else sys.maxsize)
             if idx1==l:
                 l += 1
             if idx1==0:
                 dp[0].append([n, (dp[0][-1][1] if dp[0] else 0)+1])
             else:
                 idx2 = bs(dp[idx1-1], -n, lambda _:-_[0])
                 dp[idx1].append([n, (dp[idx1][-1][1] if dp[idx1] else 0)+(dp[idx1-1][-1][1] if idx2==0 else (dp[idx1-1][-1][1]-dp[idx1-1][idx2-1][1]))])
         return dp[l-1][-1][1]