SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
128 views
in Coding Questions by Goeduhub's Expert (2.3k points)

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.

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

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

Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

Related questions

0 like 0 dislike
1 answer 653 views
0 like 0 dislike
1 answer 104 views
asked Sep 10, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 37 views
0 like 0 dislike
1 answer 133 views
asked Sep 6, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 508 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...