Problem Breakdown
We are given an array of integers and need to find how many distinct subsequences exist that have the maximum possible length among all strictly increasing ones.
Key Inputs: An integer list nums.
Output: A single integer representing the count of Longest Increasing Subsequences (LIS).
Constraints & Edge Cases:
- Strictly Increasing:
[1, 3]is valid;[1, 1]is not. This means we cannot extend a subsequence ifnums[j] >= nums[i]. - Duplicates: If the input is all identical (e.g.,
[2, 2, 2]), every single element forms an LIS of length 1. The answer should be , not just one count. - Lengths:
nums.length <= 2000. This suggests an solution is acceptable ( ops), whereas exponential solutions are impossible.
Intuition
A brute-force approach would generate all possible subsequences, check if they are increasing, calculate their lengths, and count the maximums. That takes , which is too slow for .
We need Dynamic Programming (DP). For each element nums[i], we want to know two things:
- What is the length of the longest increasing subsequence ending at index
i? Let’s call thislen[i]. - How many such subsequences exist with that specific length ending at
i? Let’s call thiscount[i].
When we process a new element nums[i], we look back at all previous elements nums[j] (where ).
- If
nums[j] < nums[i]: We can extend the subsequence ending atj.- Case 1: Extending it makes a longer sequence than what we’ve seen for
iso far (len[j] + 1 > len[i]). We updatelen[i]and resetcount[i]to matchcount[j]. - Case 2: Extending it matches the current best length found at
i(len[j] + 1 == len[i]). This means we’ve found another way to form a subsequence of this max length ending here. We addcount[j]tocount[i].
- Case 1: Extending it makes a longer sequence than what we’ve seen for
Finally, after filling our DP tables for all indices, the answer is the sum of count[i] for every index where len[i] equals the global maximum LIS length found in the array.
Approach
- Initialize two arrays:
lengthsandcounts, both size , filled with 1 (since each element itself is a subsequence of length 1). - Iterate through every index
ifrom0ton-1. - Inside, iterate backwards or forwards through all previous indices
j < i. - Apply the transition logic: if
nums[j] < nums[i]:- If
lengths[j] + 1 > lengths[i], updatelengths[i]and setcounts[i] = counts[j]. - Else if
lengths[j] + 1 == lengths[i], addcounts[j]tocounts[i].
- If
- Track the global maximum length (
max_len) encountered during iteration or find it after filling arrays. - Sum up all values in
countswhere the corresponding value inlengthsequalsmax_len.
Complexity Analysis
- Time: . We have nested loops iterating over pairs of indices with . Given constraints (), this fits within typical time limits for Python.
- Space: . We store two arrays (
lengthsandcounts) proportional to the input size.
Solution
class Solution:
def findNumberOfLIS(self, nums):
n = len(nums)
if n == 0:
return 0
# lengths[i] stores the length of LIS ending at index i
# counts[i] stores the number of such subsequences ending at index i
lengths = [1] * n
counts = [1] * n
max_len = 0
for i in range(n):
current_max_len_at_i = 0
for j in range(i):
if nums[j] < nums[i]:
# If we can extend a longer subsequence found at j
if lengths[j] + 1 > lengths[i]:
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
elif lengths[j] + 1 == lengths[i]:
# Found another way to achieve the same max length ending here
counts[i] += counts[j]
if lengths[i] > max_len:
max_len = lengths[i]
total_count = 0
for i in range(n):
if lengths[i] == max_len:
total_count += counts[i]
return total_count
Edge Cases Handled
- All Duplicates: The logic ensures
lengthsstays at 1, and since every element is valid (strictly increasing condition fails for duplicates), the code correctly sums all elements as they each form a length-1 LIS. - Strictly Increasing Array: Only one path exists to build the sequence; counts propagate exactly once per level, resulting in
total_count = 1. - Decreasing Array: No element can extend another (
nums[j] < nums[i]never true). All lengths remain 1. Max length is 1. Sum of counts for all indices equals .