# 673. Number of Longest Increasing Subsequence
Given an unsorted array of integers, find the number of longest increasing subsequence.
Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
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.
Approach 1: the number of LIS consists of 2 parts -- the sequences that ends with the same item, and sequences that ends with different items.
# Code (Python)
class Solution: def findNumberOfLIS(self, nums): if not nums: return 0 # longest subsequence ending with nums[i] longest = [1 for _ in range(len(nums))] # number of longest subsequences ending with nums[i] num_longest = [1 for _ in range(len(nums))] # global length of LIS global_max_length = 1 # global number of LIS global_num_max_length = 1 for i in range(1, len(nums)): for j in range(i): if nums[j] >= nums[i]: continue if longest[j] + 1 == longest[i]: num_longest[i] += num_longest[j] elif longest[j] + 1 > longest[i]: longest[i] = longest[j] + 1 num_longest[i] = num_longest[j] if global_max_length == longest[i]: global_num_max_length += num_longest[i] elif global_max_length < longest[i]: global_max_length = longest[i] global_num_max_length = num_longest[i] return global_num_max_length
# Code (C++)