Number of Longest Increasing Subsequence Problem

Question

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.

Answer 1

In the Longest Increasing Subsequence problem, the DP array simply had to store the longest length. In this variant, each element in the DP array needs to store two things: (1) Length of longest subsequence ending at this index and (2) Number of longest subsequences that end at this index. I use a two element list for this purpose.

In each loop as we build up the DP array, find the longest length for this index and then sum up the numbers at these indices that contribute to this longest length.

class Solution(object):     def findNumberOfLIS(self, nums):         """         :type nums: List[int]         :rtype: int         """         # Time: O(n^2)         # Space: O(n)         dp, longest = [[1, 1] for i in range(len(nums))], 1         for i, num in enumerate(nums):             curr_longest, count = 1, 0             for j in range(i):                 if nums[j] < num:                     curr_longest = max(curr_longest, dp[j][0] + 1)             for j in range(i):                 if dp[j][0] == curr_longest - 1 and nums[j] < num:                     count += dp[j][1]             dp[i] = [curr_longest, max(count, dp[i][1])]             longest = max(curr_longest, longest)         return sum([item[1] for item in dp if item[0] == longest])

eg : ans = Solution()

ans.findNumberOfLIS([1,3,5,4,7])

Output -

2