Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Examples

Example 1:

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].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The longest increasing subsequence is of length 1, and there are 5 subsequences of length 1, so return 5.

Constraints

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

Thinking Process

  1. Dual DP Arrays: Need both length (dp) and count (cnt) arrays
    • Longer subsequence → reset count
    • Equal-length subsequence → accumulate count
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

Solution: Dynamic Programming with Count Tracking

class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        if n == 0:
            return 0

        dp = [1] * n
        cnt = [1] * n

        maxLen = 1
        rtn = 0

        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:

                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]

                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]

            if dp[i] > maxLen:
                maxLen = dp[i]
                rtn = cnt[i]
            elif dp[i] == maxLen:
                rtn += cnt[i]

        return rtn

Solution Explanation

Approach: 1D DP (this problem)

Key idea: 1. Dual DP Arrays: Need both length (dp) and count (cnt) arrays

How the code works:

  1. Dual DP Arrays: Need both length (dp) and count (cnt) arrays
    • Longer subsequence → reset count
    • Equal-length subsequence → accumulate count
    • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
    • Recurrence: how does the answer build from smaller indices?
    • Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input nums = [1,3,5,4,7], expected output 2:

The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Algorithm Explanation:

  1. Initialize (Lines 5-7):
    • dp[i] = 1: Each element forms a subsequence of length 1
    • cnt[i] = 1: Each element has 1 subsequence ending at it
    • maxLen = 1: Track maximum length found so far
    • rtn = 0: Accumulate count of longest subsequences
  2. For Each Position i (Lines 8-22):
    • Check all previous positions j (Lines 9-18):
      • If nums[i] > nums[j] (can extend subsequence):
        • If dp[j] + 1 > dp[i] (Line 11): Found longer subsequence
          • Update dp[i] = dp[j] + 1
          • Reset cnt[i] = cnt[j] (new longest, so count comes from j)
        • Else if dp[j] + 1 == dp[i] (Line 14): Found equal-length subsequence
          • Add cnt[j] to cnt[i] (accumulate counts)
    • Update Global Maximum (Lines 19-23):
      • If dp[i] > maxLen: Found longer subsequence → update maxLen and reset rtn = cnt[i]
      • Else if dp[i] == maxLen: Add cnt[i] to rtn
  3. Return (Line 24): Total count of longest increasing subsequences

Why This Works:

  • Length Tracking: dp[i] tracks the length of LIS ending at position i (same as LC 300)
  • Count Accumulation: cnt[i] accumulates the number of ways to form LIS of length dp[i] ending at i
  • Two Cases:
    • Longer subsequence found: Reset count (only count the longest ones)
    • Equal-length subsequence found: Add counts (multiple ways to reach same length)
  • Final Sum: Sum all counts for positions with maximum length

Example Walkthrough:

For nums = [1,3,5,4,7]:

Initial: dp = [1,1,1,1,1], cnt = [1,1,1,1,1], maxLen = 1, rtn = 0

i=0: nums[0]=1
  - No previous positions
  - dp[0]=1, maxLen=1, rtn=1

i=1: nums[1]=3
  - j=0: 3 > 1 → dp[0]+1=2 > dp[1]=1
    - dp[1] = 2, cnt[1] = cnt[0] = 1
  - dp[1]=2 > maxLen=1 → maxLen=2, rtn=cnt[1]=1

i=2: nums[2]=5
  - j=0: 5 > 1 → dp[0]+1=2 > dp[2]=1
    - dp[2] = 2, cnt[2] = cnt[0] = 1
  - j=1: 5 > 3 → dp[1]+1=3 > dp[2]=2
    - dp[2] = 3, cnt[2] = cnt[1] = 1
  - dp[2]=3 > maxLen=2 → maxLen=3, rtn=cnt[2]=1

i=3: nums[3]=4
  - j=0: 4 > 1 → dp[0]+1=2 > dp[3]=1
    - dp[3] = 2, cnt[3] = cnt[0] = 1
  - j=1: 4 > 3 → dp[1]+1=3 == dp[3]=2
    - dp[3] = 3, cnt[3] += cnt[1] = 1 + 1 = 2
  - j=2: 4 ≤ 5 (skip)
  - dp[3]=3 == maxLen=3 → rtn += cnt[3] = 1 + 2 = 3

i=4: nums[4]=7
  - j=0: 7 > 1 → dp[0]+1=2 > dp[4]=1
    - dp[4] = 2, cnt[4] = cnt[0] = 1
  - j=1: 7 > 3 → dp[1]+1=3 > dp[4]=2
    - dp[4] = 3, cnt[4] = cnt[1] = 1
  - j=2: 7 > 5 → dp[2]+1=4 > dp[4]=3
    - dp[4] = 4, cnt[4] = cnt[2] = 1
  - j=3: 7 > 4 → dp[3]+1=4 == dp[4]=4
    - dp[4] = 4, cnt[4] += cnt[3] = 1 + 2 = 3
  - dp[4]=4 > maxLen=3 → maxLen=4, rtn=cnt[4]=3

Wait, let me recalculate. Actually, the longest should be length 4, and there should be 2 subsequences:
[1,3,4,7] and [1,3,5,7]

Let me trace more carefully:

i=0: dp[0]=1, cnt[0]=1, maxLen=1, rtn=1
i=1: dp[1]=2 (from 0), cnt[1]=1, maxLen=2, rtn=1
i=2: dp[2]=3 (from 1), cnt[2]=1, maxLen=3, rtn=1
i=3: dp[3]=3 (from 1), cnt[3]=1, maxLen=3, rtn=1+1=2
i=4: dp[4]=4 (from 2 or 3), cnt[4]=cnt[2]+cnt[3]=1+1=2, maxLen=4, rtn=2

Actually, let me verify with the code logic more carefully.

Let me provide a clearer walkthrough:

For nums = [1,3,5,4,7]:

i nums[i] j nums[j] Condition dp[j]+1 vs dp[i] dp[i] cnt[i] maxLen rtn
0 1 - - - - 1 1 1 1
1 3 0 1 3>1 2 > 1 2 1 2 1
2 5 0 1 5>1 2 > 1 2 1 2 1
2 5 1 3 5>3 3 > 2 3 1 3 1
3 4 0 1 4>1 2 > 1 2 1 3 1
3 4 1 3 4>3 3 == 2 3 1+1=2 3 1+2=3
3 4 2 5 4≤5 skip 3 2 3 3
4 7 0 1 7>1 2 > 1 2 1 3 3
4 7 1 3 7>3 3 > 2 3 1 3 3
4 7 2 5 7>5 4 > 3 4 1 4 1
4 7 3 4 7>4 4 == 4 4 1+2=3 4 1+3=4

Wait, this doesn’t match the expected output of 2. Let me reconsider…

Actually, the issue is that when we check j=2 and j=3 for i=4, both can extend to length 4:

  • From j=2 (5): [1,3,5,7] → length 4
  • From j=3 (4): [1,3,4,7] → length 4

So cnt[4] should be cnt[2] + cnt[3] = 1 + 2 = 3? But the expected answer is 2.

Let me think about this differently. The actual longest subsequences are:

  • [1,3,5,7] (one way)
  • [1,3,4,7] (one way)

So there are 2 subsequences. But why would cnt[3]=2? Let me check…

For i=3 (value 4):

  • Can extend from j=0 (1): [1,4] → length 2
  • Can extend from j=1 (3): [1,3,4] → length 3

So dp[3]=3, and there’s only 1 way: [1,3,4]. So cnt[3] should be 1, not 2.

Let me recalculate more carefully:

i=0: dp[0]=1, cnt[0]=1
i=1: 
  - j=0: 3>1, dp[0]+1=2 > dp[1]=1 → dp[1]=2, cnt[1]=cnt[0]=1
i=2:
  - j=0: 5>1, dp[0]+1=2 > dp[2]=1 → dp[2]=2, cnt[2]=cnt[0]=1
  - j=1: 5>3, dp[1]+1=3 > dp[2]=2 → dp[2]=3, cnt[2]=cnt[1]=1
i=3:
  - j=0: 4>1, dp[0]+1=2 > dp[3]=1 → dp[3]=2, cnt[3]=cnt[0]=1
  - j=1: 4>3, dp[1]+1=3 == dp[3]=2 → dp[3]=3, cnt[3]=cnt[1]=1
  - j=2: 4≤5, skip
i=4:
  - j=0: 7>1, dp[0]+1=2 > dp[4]=1 → dp[4]=2, cnt[4]=cnt[0]=1
  - j=1: 7>3, dp[1]+1=3 > dp[4]=2 → dp[4]=3, cnt[4]=cnt[1]=1
  - j=2: 7>5, dp[2]+1=4 > dp[4]=3 → dp[4]=4, cnt[4]=cnt[2]=1
  - j=3: 7>4, dp[3]+1=4 == dp[4]=4 → dp[4]=4, cnt[4]=cnt[2]+cnt[3]=1+1=2

So final: maxLen=4, rtn=2. This matches!

Complexity Analysis:

  • Time Complexity: O(n²)
    • For each of n positions, check all previous positions
    • Total: O(n × n) = O(n²)
  • Space Complexity: O(n)
    • Two arrays dp and cnt of size n
    • O(1) extra variables

Example Walkthrough (Corrected):

For nums = [1,3,5,4,7]:

Step-by-step:

i=0: nums[0]=1
  dp[0]=1, cnt[0]=1
  maxLen=1, rtn=1

i=1: nums[1]=3
  j=0: 3 > 1 → dp[0]+1=2 > dp[1]=1
    dp[1]=2, cnt[1]=cnt[0]=1
  dp[1]=2 > maxLen=1 → maxLen=2, rtn=1

i=2: nums[2]=5
  j=0: 5 > 1 → dp[0]+1=2 > dp[2]=1
    dp[2]=2, cnt[2]=cnt[0]=1
  j=1: 5 > 3 → dp[1]+1=3 > dp[2]=2
    dp[2]=3, cnt[2]=cnt[1]=1
  dp[2]=3 > maxLen=2 → maxLen=3, rtn=1

i=3: nums[3]=4
  j=0: 4 > 1 → dp[0]+1=2 > dp[3]=1
    dp[3]=2, cnt[3]=cnt[0]=1
  j=1: 4 > 3 → dp[1]+1=3 == dp[3]=2
    dp[3]=3, cnt[3]=cnt[1]=1
  j=2: 4 ≤ 5 (skip)
  dp[3]=3 == maxLen=3 → rtn += cnt[3] = 1 + 1 = 2

i=4: nums[4]=7
  j=0: 7 > 1 → dp[0]+1=2 > dp[4]=1
    dp[4]=2, cnt[4]=cnt[0]=1
  j=1: 7 > 3 → dp[1]+1=3 > dp[4]=2
    dp[4]=3, cnt[4]=cnt[1]=1
  j=2: 7 > 5 → dp[2]+1=4 > dp[4]=3
    dp[4]=4, cnt[4]=cnt[2]=1
  j=3: 7 > 4 → dp[3]+1=4 == dp[4]=4
    dp[4]=4, cnt[4]=cnt[2]+cnt[3]=1+1=2
  dp[4]=4 > maxLen=3 → maxLen=4, rtn=cnt[4]=2

Final result: 2

The two longest increasing subsequences are:

  • [1,3,5,7] (extending from position 2)
  • [1,3,4,7] (extending from position 3)

    Common Mistakes

  1. All same elements: nums = [2,2,2,2,2] → return 5 (each element is a subsequence of length 1)
  2. Strictly increasing: nums = [1,2,3,4,5] → return 1 (only one LIS)
  3. Single element: nums = [1] → return 1

  4. Multiple paths: nums = [1,3,5,4,7] → return 2 (two ways to form length 4)

  5. Not resetting count: When finding longer subsequence, must reset cnt[i] = cnt[j], not add
  6. Wrong accumulation: Only accumulate when lengths are equal, not when longer
  7. Missing final sum: Must sum all cnt[i] where dp[i] == maxLen
  8. Initialization error: Both dp and cnt should be initialized to 1

This problem extends LC 300 by adding count tracking. The key is maintaining both length and count information, and correctly handling the two cases: when a longer subsequence is found (reset count) and when an equal-length subsequence is found (accumulate count).

Key Takeaways

  1. Dual DP Arrays: Need both length (dp) and count (cnt) arrays
  2. Two Update Cases:
    • Longer subsequence → reset count
    • Equal-length subsequence → accumulate count
  3. Count Accumulation: When multiple paths lead to same length, sum their counts
  4. Final Sum: Sum all counts for positions with maximum length

References

Template Reference