Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 673 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 673 # by problem number
lcpy gen -s number_of_longest_increasing_subsequence # by problem name
nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
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].
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
class Solution:
# Time: O(n^2)
# Space: O(n)
def find_number_of_lis(self, nums: list[int]) -> int:
n = len(nums)
length = [1] * n
count = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if length[j] + 1 > length[i]:
length[i] = length[j] + 1
count[i] = count[j]
elif length[j] + 1 == length[i]:
count[i] += count[j]
best = max(length)
return sum(c for length_i, c in zip(length, count, strict=True) if length_i == best)
| Time | Space |
|---|---|
| O(n^2) | O(n) |