Leetcode 673. Number of Longest Increasing Subsequence (Python)

Related Topic

Dynamic-Programming.

Description

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

Sample I/O

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.

Methodology

This question can be solved by Dynamic Programming. It is similar with question 300. Longest Increasing Subsequence. But now, the question is asking how many numbers of the longest increasing subsequence.

I personally think this question should belong to hard level.

To get the answer, we need to build connection between length of the longest increasing subsequence and the count the of length. For that, we need to get current element’s length of longest increasing subsequence and meanwhile we also need to know the current element’s count of longest increasing subsequence. It’s bit of tricky here, think twice. The answer is sum up each longest increasing subsequence’s count.

Find the base case:

We need two dp list here, one is for the length of the longest increaseing subsequence and each element represent the current longest length. Another one is for counting the number of such sequence and each element represent the count of increasing of include element. length and count are at least 1 unless there is no input length = [1]n count = [1]n

Find the pattern:

The length is easy to come up. If the current element is greater than before (make the subsequence increasing), then we will get the max length of previous plus 1. Else just stay in 1(Not increasing).

The count is hard to understand. The current element is the sum of previous longest increasing subsequence whose max element is less than current element(this will make the current subsequence keep increasing and also means the previous longest increasing subsequences’ length is 1 less than the current longest increasing subsequence)

Answer:

Return the value from count that element is bigest element in length

Code 1 (Inheriate code from question 334)

def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1: return N
        lengths = [1] * N #lengths[i] = longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for i, num in enumerate(nums):
            for j in range(i):
                if nums[j] < nums[i]:
                    if lengths[j] >= lengths[i]:
                        lengths[i] = max(lengths[i],lengths[j]+1)
                        counts[i] = counts[j]
                    elif lengths[i]==lengths[j] + 1:
                        counts[i] += counts[j]
        longest = max(lengths)
        return sum(c for j, c in enumerate(counts) if lengths[j] == longest)

BigO

Create dp list will cost O(2n) and iterate the dp will cost ((n-1)*n) in total will be O((n-1)*n+2n)