Number of Longest Increasing Subsequence — LeetCode 673 Python Solution

The problem

Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.

Example

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].

Python solution

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1] * n
        cnt = [1] * n
        mx = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i] = f[j] + 1
                        cnt[i] = cnt[j]
                    elif f[i] == f[j] + 1:
                        cnt[i] += cnt[j]
            if mx < f[i]:
                mx = f[i]
                ans = cnt[i]
            elif mx == f[i]:
                ans += cnt[i]
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 673. Number of Longest Increasing Subsequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems