673. Number of Longest Increasing Subsequence

Problem Statement

link: https://leetcode.com/problems/number-of-longest-increasing-subsequence/ https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

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

Input: nums = [2,2,2,2,2] Output: 5

Input: head = [] Output: []

Solution Approach

The algorithm uses dynamic programming to compute the length and count of the longest increasing subsequences for each element, and then aggregates the counts for the longest subsequences found.

Algorithm

1. Dynamic Programming Arrays: The algorithm uses two arrays—lengths to store the length of the longest increasing subsequence ending at each index, and counts to store the number of such subsequences.
2. Comparative Updates: For each element, it compares with all previous elements to update the lengths and counts arrays, ensuring that all possible increasing subsequences are considered.
3. Final Aggregation: It finds the maximum length of the increasing subsequences and sums up the counts of subsequences that match this maximum length to determine the total number of longest increasing subsequences.

Complexity

time complexity: O(n^2) space complexity: O(n)

Implement

    from bisect import bisect_left from typing import List, Callable
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        lengths = [0] * n  # lengths[i] = length of the longest ending in nums[i]
        counts = [1] * n   # counts[i] = number of LIS ending in nums[i]

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

        longest = max(lengths)
        return sum(c for l, c in zip(lengths, counts) if l == longest)

    
    

Twitter  facebook  Email