Problem Description

Given an integer array nums, you need to find and return the total count of longest increasing subsequences in the array.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. An increasing subsequence means each element must be strictly greater than the previous one (no equal values allowed).

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

• The longest increasing subsequences have length 4
• There are two such subsequences: [1, 3, 5, 7] and [1, 3, 4, 7]
• So the answer would be 2

The task is to count how many different longest increasing subsequences exist in the array. If multiple subsequences share the maximum length, count all of them.

Intuition

To solve this problem, we need to track two things simultaneously: the length of the longest increasing subsequence ending at each position, and how many such subsequences exist.

Think about building increasing subsequences step by step. For each element nums[i], we can either start a new subsequence with just this element, or extend existing subsequences that end with smaller values.

The key insight is that when we're at position i, we need to look back at all previous positions j where nums[j] < nums[i]. Each of these positions represents a potential way to extend a subsequence.

For each valid previous position j:

• If extending from j gives us a longer subsequence than we've found so far ending at i, we've discovered a new optimal length. We update our length and reset our count to match the count from position j.
• If extending from j gives us the same length as our current best, we've found additional ways to form subsequences of the optimal length. We add the count from position j to our current count.

This naturally leads to using two arrays: f[i] to store the length of the longest subsequence ending at position i, and cnt[i] to store how many such subsequences exist.

As we process the entire array, we also maintain global tracking of the overall longest length found and accumulate counts whenever we encounter subsequences matching this maximum length. This way, we can return the total count of all longest increasing subsequences in the array.

The dynamic programming nature emerges from reusing previously computed results - we build upon the optimal solutions for earlier positions to find optimal solutions for later positions.

Learn more about Segment Tree and Dynamic Programming patterns.

Solution Approach

We implement a dynamic programming solution using two arrays to track the necessary information:

1. Initialize arrays: Create two arrays f and cnt, both of size n:

   • f[i] stores the length of the longest increasing subsequence ending at position i
   • cnt[i] stores the count of such longest subsequences ending at position i
   • Initialize both arrays with value 1, since each element alone forms a subsequence of length 1

2. Track global maximum: Maintain variables mx (maximum length found) and ans (count of subsequences with maximum length)

3. Build the DP solution: For each position i from 0 to n-1:

   • Examine all previous positions j from 0 to i-1
   • If nums[j] < nums[i], we can extend the subsequence from position j:
     • If f[i] < f[j] + 1: We found a longer subsequence
       • Update f[i] = f[j] + 1 (new length)
       • Set cnt[i] = cnt[j] (inherit the count from position j)
     • If f[i] == f[j] + 1: We found another way to form a subsequence of the same optimal length
       • Add to the count: cnt[i] += cnt[j]

4. Update global answer: After processing all positions j for current i:

   • If mx < f[i]: We found a new global maximum length
     • Update mx = f[i]
     • Reset ans = cnt[i]
   • If mx == f[i]: We found more subsequences with the maximum length
     • Add to the answer: ans += cnt[i]

5. Return result: After processing all positions, ans contains the total count of longest increasing subsequences

The time complexity is O(n²) due to the nested loops, and space complexity is O(n) for the two arrays.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 5, 4, 7]:

Initial Setup:

• Arrays f and cnt both start as [1, 1, 1, 1, 1] (each element forms a subsequence of length 1)
• mx = 0, ans = 0

Processing i = 0 (nums[0] = 1):

• No previous elements to check
• After processing: f[0] = 1, cnt[0] = 1
• Update globals: mx = 1, ans = 1

Processing i = 1 (nums[1] = 3):

• Check j = 0: nums[0] = 1 < 3 ✓
  • f[1] = 1 < f[0] + 1 = 2, so update: f[1] = 2, cnt[1] = 1
• After processing: f[1] = 2, cnt[1] = 1
• Update globals: mx = 2, ans = 1

Processing i = 2 (nums[2] = 5):

• Check j = 0: nums[0] = 1 < 5 ✓
  • f[2] = 1 < f[0] + 1 = 2, so update: f[2] = 2, cnt[2] = 1
• Check j = 1: nums[1] = 3 < 5 ✓
  • f[2] = 2 < f[1] + 1 = 3, so update: f[2] = 3, cnt[2] = 1
• After processing: f[2] = 3, cnt[2] = 1
• Update globals: mx = 3, ans = 1

Processing i = 3 (nums[3] = 4):

• Check j = 0: nums[0] = 1 < 4 ✓
  • f[3] = 1 < f[0] + 1 = 2, so update: f[3] = 2, cnt[3] = 1
• Check j = 1: nums[1] = 3 < 4 ✓
  • f[3] = 2 < f[1] + 1 = 3, so update: f[3] = 3, cnt[3] = 1
• Check j = 2: nums[2] = 5 > 4 ✗ (skip)
• After processing: f[3] = 3, cnt[3] = 1
• Update globals: mx = 3, ans = 1 + 1 = 2 (another subsequence of length 3)

Processing i = 4 (nums[4] = 7):

• Check j = 0: nums[0] = 1 < 7 ✓
  • f[4] = 1 < f[0] + 1 = 2, so update: f[4] = 2, cnt[4] = 1
• Check j = 1: nums[1] = 3 < 7 ✓
  • f[4] = 2 < f[1] + 1 = 3, so update: f[4] = 3, cnt[4] = 1
• Check j = 2: nums[2] = 5 < 7 ✓
  • f[4] = 3 < f[2] + 1 = 4, so update: f[4] = 4, cnt[4] = 1
• Check j = 3: nums[3] = 4 < 7 ✓
  • f[4] = 4 == f[3] + 1 = 4, so add counts: cnt[4] = 1 + 1 = 2
• After processing: f[4] = 4, cnt[4] = 2
• Update globals: mx = 4, ans = 2

Final State:

• f = [1, 2, 3, 3, 4] (lengths of longest subsequences ending at each position)
• cnt = [1, 1, 1, 1, 2] (counts of such subsequences)
• Answer: 2 (two longest increasing subsequences of length 4)

The two subsequences are [1, 3, 5, 7] and [1, 3, 4, 7], both captured by our count at position 4.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the array nums. This is because we have two nested loops - the outer loop iterates through all indices i from 0 to n-1, and for each i, the inner loop iterates through all indices j from 0 to i-1. This results in approximately n * (n-1) / 2 comparisons, which simplifies to O(n^2).

The space complexity is O(n), where n is the length of the array nums. The algorithm uses two auxiliary arrays f and cnt, each of size n, to store the length of the longest increasing subsequence ending at each position and the count of such subsequences respectively. Additionally, a few constant space variables (mx, ans, i, j) are used, but these don't affect the overall space complexity. Therefore, the total space complexity is O(n) + O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Forgetting to Update Count When Finding Equal Length Subsequences

One of the most common mistakes in this problem is incorrectly handling the count array when multiple subsequences of the same length can end at position i. Developers often forget to accumulate counts from all valid previous positions.

Incorrect Implementation:

for j in range(i):
    if nums[j] < nums[i]:
        if dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
            count[i] = count[j]  # Only storing the last count

This implementation overwrites count[i] each time instead of accumulating when finding multiple paths of the same optimal length.

Correct Implementation:

for j in range(i):
    if nums[j] < nums[i]:
        if dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
            count[i] = count[j]  # Reset count for new maximum
        elif dp[i] == dp[j] + 1:
            count[i] += count[j]  # Accumulate count for equal length

Pitfall: Incorrect Initialization of Count Array

Another mistake is initializing the count array to 0 instead of 1. Each element by itself forms a valid subsequence of length 1, so there's always at least one subsequence ending at each position.

Incorrect:

count = [0] * n  # Wrong: missing the single-element subsequences

Correct:

count = [1] * n  # Each element counts as one subsequence of length 1

Pitfall: Not Handling the Final Answer Accumulation Properly

Some implementations incorrectly return count[n-1] or max(count) instead of properly accumulating all counts that correspond to the maximum length.

Incorrect:

return count[n-1]  # Wrong: only considers subsequences ending at last position

Correct:

for i in range(n):
    # ... DP logic ...
    if max_length < dp[i]:
        max_length = dp[i]
        result = count[i]
    elif max_length == dp[i]:
        result += count[i]  # Accumulate all subsequences with max length
return result

These pitfalls can lead to undercounting the total number of longest increasing subsequences, producing incorrect results even when the algorithm correctly identifies the maximum length.