NeetCode #683LC-673Medium1-D Dynamic Programming
← Back to All Problems#683 · #673 · Number of Longest Increasing Subsequence(最长递增子序列的个数)
📌 Problem Statement & Constraints
Given an integer array
nums, return the number of longest strictly increasing subsequences. Constraints: 1 <= nums.length <= 2000, -10^6 <= nums[i] <= 10^6, and the answer fits in a 32-bit integer.💡 Core Algorithmic Approaches
- Track two arrays:
length[i], the length of the longest increasing subsequence ending ati, andcount[i], the number of such subsequences. - For each pair
j < iwithnums[j] < nums[i], comparelength[j] + 1withlength[i]. - If it is larger, reset
length[i]and copycount[j]; if it is equal, addcount[j]tocount[i]. - Finally sum the counts of all indices whose
lengthequals the global maximum.
💻 Benchmark Python3 Implementation
class Solution:
def findNumberOfLIS(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 l, c in zip(length, count) if l == best)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the nested loop over pairs.
💾 Space Complexity
O(n): two arrays.
⚠️ Interview Pitfalls & Follow-ups
- Overwriting the count on a tie: when a new predecessor yields the same length, the counts must be added, not replaced.
- Summing every count: only indices whose
lengthequals the global maximum contribute. - Using a non-strict comparison: equal values do not extend an increasing subsequence, so the test is
nums[j] < nums[i]. - Expecting the O(n log n) patience array to give the count:
tailsencodes lengths only, so a separate DP is needed for counting.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.