673. Number of Longest Increasing Subsequence

Medium

---

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

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

Example 2:

Input: nums = [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.

Constraints:

• 1 <= nums.length <= 2000

• -106 <= nums[i] <= 106

Solution is exactly same as Problem 300 : Longest Increasing Subsequence

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums: 
            return 0
        decks, ends_decks, paths = [], [], []
        for num in nums:
            deck_idx = bisect.bisect_left(ends_decks, num)
            n_paths = 1
            # print('Deck id', deck_idx)
            if deck_idx > 0:
                l = bisect.bisect(decks[deck_idx-1], -num)
                n_paths = paths[deck_idx-1][-1] - paths[deck_idx-1][l]
            # print("n Paths", n_paths)
            if deck_idx == len(decks):
                decks.append([-num])
                ends_decks.append(num)
                paths.append([0,n_paths])
            else:
                decks[deck_idx].append(-num)
                ends_decks[deck_idx] = num
                paths[deck_idx].append(n_paths + paths[deck_idx][-1])
            # print(decks)
            # print(paths)
            # print(ends_decks)
            # print("="*10)
        return paths[-1][-1]