⚡Flashcard Drill➔
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

  1. Track two arrays: length[i], the length of the longest increasing subsequence ending at i, and count[i], the number of such subsequences.
  2. For each pair j < i with nums[j] < nums[i], compare length[j] + 1 with length[i].
  3. If it is larger, reset length[i] and copy count[j]; if it is equal, add count[j] to count[i].
  4. Finally sum the counts of all indices whose length equals 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 length equals 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: tails encodes 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems