Dynamic Programming: Number of Longest Increasing Subsequences (LIS Count)

This chapter addresses the classic problem of finding not just the maximum length of a Longest Increasing Subsequence (LIS), but the total count of all such unique longest increasing subsequences in a given array. It builds directly upon the foundational LIS algorithms (DP 41 and DP 42).

1. Why Do We Need This? (Problem Statement & Status Quo)

In standard LIS problems, the objective is singular: Find the maximum length of a strictly increasing subsequence.

• Status Quo (DP 41/42): We use a single dp array where dp[i] stores the length of the LIS ending at index i.
• The Missing Link: Suppose an array has an LIS of length 4. There might be multiple distinct subsequences that achieve this exact length.
• The Goal: Given an array, output the total number of distinct increasing subsequences that share the maximum length found in the array.

Example Walkthrough

Consider the array: [1, 3, 5, 4, 7]

• LIS Length: 4
• Possible LIS Paths:
  1. [1, 3, 4, 7] (Length = 4)
  2. [1, 3, 5, 7] (Length = 4)
• Total Number of LIS: 2

2. Core Mental Model: Maintaining a Parallel Count Array

To track how many ways we can form an LIS ending at each index, we cannot rely on the dp array alone. We must introduce a parallel count array.

The Dual-Array Strategy

1. dp[i]: Stores the maximum length of the LIS ending at index i.
2. count[i]: Stores the total number of LIS of length dp[i] that end at index i.

Initialization Rule

Every single element in the array is, by default, an increasing subsequence of length 1 with exactly 1 way to form it.

• dp[i] = 1 for all i
• count[i] = 1 for all i

3. Naive vs. Better Approach: Updating Lengths and Counts

When iterating through the array to build our solution for index i, we look back at all previous elements j (where j < i). Two primary scenarios dictate how we update our dp and count values:

Current Element (arr[i])
       ^
       | checks all previous elements (arr[j])
       |
Previous Element (arr[j])

Scenario A: Finding a Longer Subsequence (dp[j] + 1 > dp[i])

If we encounter a previous element arr[j] that is smaller than arr[i] (arr[j] < arr[i]), and appending arr[i] to the sequence ending at j yields a strictly greater length, we update both length and inherit the count:

• dp[i] = dp[j] + 1
• count[i] = count[j] (Reset count because we found a longer path)

Scenario B: Finding an Alternative Path of Equal Length (dp[j] + 1 == dp[i])

If appending arr[i] to the sequence ending at j yields a length equal to the current dp[i], it means we found an alternative route of the exact same length.

• dp[i] remains unchanged.
• count[i] += count[j] (Accumulate ways from the alternative path)

4. Step-by-Step Evolution: Manual Dry Run

Let's trace the algorithm on a small array: [1, 3, 5, 4, 7]

Step 0: Initialization

• Array: [1, 3, 5, 4, 7]
• dp: [1, 1, 1, 1, 1]
• count: [1, 1, 1, 1, 1]

Step 1: Processing Index 1 (Value: 3)

• Look back at index 0 (value: 1). Since 1 < 3:
  • dp[1] = dp[0] + 1 = 2
  • count[1] = count[0] = 1
• State:
  • dp: [1, 2, 1, 1, 1]
  • count: [1, 1, 1, 1, 1]

Step 2: Processing Index 2 (Value: 5)

• Look back at 0 (1) and 1 (3).
  • Via 0: dp[0] + 1 = 2 (Less than current max, or handled).
  • Via 1: dp[1] + 1 = 3. Since 3 > dp[2]:
    • dp[2] = 3
    • count[2] = count[1] = 1
• State:
  • dp: [1, 2, 3, 1, 1]
  • count: [1, 1, 1, 1, 1]

Step 3: Processing Index 3 (Value: 4)

• Look back at 0 (1), 1 (3), and 2 (5).
  • Via 1 (3): dp[1] + 1 = 3. Since 3 > dp[3]:
    • dp[3] = 3
    • count[3] = count[1] = 1
  • Via 2 (5): 5 > 4, so we cannot attach.
• State:
  • dp: [1, 2, 3, 3, 1]
  • count: [1, 1, 1, 1, 1]

Step 4: Processing Index 4 (Value: 7)

• Look back at all previous elements:
  • Via 1 (3): dp[1] + 1 = 3 (Equal to current length 3 if we check 5 or 4).
  • Let's check 2 (5): dp[2] + 1 = 4. Since 4 > dp[4]:
    • dp[4] = 4
    • count[4] = count[2] = 1 ([1, 3, 5, 7])
  • Via 3 (4): dp[3] + 1 = 4. Since 4 == dp[4] (equal length!):
    • Accumulate count: count[4] += count[3] (1 + 1 = 2) ([1, 3, 4, 7])

5. Real-World Practical Pitfalls & Edge Cases

When implementing this algorithm in production, keep these edge cases in mind:

6. Complete Flow Walkthrough

7. C++ Implementation

Here is the complete, clean C++ implementation reflecting the logic discussed above:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;

        vector<int> dp(n, 1);
        vector<int> count(n, 1);
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    // Case 1: Found a strictly longer subsequence path
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j]; // Inherit count
                    }
                    // Case 2: Found an alternative path of the exact same length
                    else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j]; // Accumulate count
                    }
                }
            }
            maxLen = max(maxLen, dp[i]);
        }

        // Aggregate total number of LIS matching maxLen
        int totalLIS = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                totalLIS += count[i];
            }
        }

        return totalLIS;
    }
};

Summary and Key Takeaways

• Extension of Standard LIS: Finding the number of LIS requires building upon traditional LIS logic by adding a parallel frequency tracking array (count).
• Dual-State Logic: Maintain dp[i] for the maximum length ending at i and count[i] for the number of ways to reach that length.
• Strictly Greater vs. Equal:
  • When dp[j] + 1 > dp[i], update the length and reset/inherit the count.
  • When dp[j] + 1 == dp[i], keep the length and accumulate (+=) the count.
• Global Summation: The longest increasing subsequence does not necessarily end at the last index of the array; always scan the entire dp array to find maxLen.
• Final Result: Sum up all count[i] entries where dp[i] equals the global maximum LIS length.