Number of Longest Increasing Subsequences

Problem Statement

Given an integer array nums, find the number of Longest Increasing Subsequences (LIS) in the array.

Examples

Example 1:

Input: nums = [1, 3, 5, 4, 7]
Output: 2

Explanation: There are two LIS of length 4:
[1, 3, 4, 7]
[1, 3, 5, 7]

Example 2:

Input: nums = [2, 2, 2, 2, 2]
Output: 5

Explanation: All elements are the same, so every single element can form an LIS of length 1. There are 5 such subsequences.

Different Approaches

1️⃣ Recursion (TLE)

Intuition:

Try every subsequence using recursion. Track:

• Max length of LIS found so far
• Count of how many LIS match that length

Code:

class Solution {
public:
    int count = 0;  // To count how many LIS of maximum length exist
    int maxi = 0;   // To track the length of the Longest Increasing Subsequence (LIS)

    // Recursive DFS to explore all possible increasing subsequences
    void dfs(int index, vector<int>& nums, vector<int>& path) {
        // Base case: if we've reached the end of the array
        if (index == nums.size()) {
            // If current path is longer than previous maximum, update max and reset count
            if (path.size() > maxi) {
                maxi = path.size();
                count = 1;
            }
            // If it's equal to max length, increment the count
            else if (path.size() == maxi) {
                count++;
            }
            return;
        }

        // ✅ CHOICE 1: Include the current element if it forms an increasing subsequence
        // (i.e., it's larger than the last element in the current path)
        if (path.empty() || nums[index] > path.back()) {
            path.push_back(nums[index]);     // include current element
            dfs(index + 1, nums, path);      // explore further with it included
            path.pop_back();                 // backtrack (remove the element after exploring)
        }

        // ✅ CHOICE 2: Exclude the current element and move to next index
        dfs(index + 1, nums, path);
    }

    // Entry point: initializes DFS
    int numberOfLIS(vector<int> nums) {
        vector<int> path;       // Holds the current subsequence
        dfs(0, nums, path);     // Start DFS from index 0
        return count;           // Return total count of longest increasing subsequences
    }
};

Complexity Analysis:

• Time Complexity: O(2^n)
• Space Complexity: O(n)
  • Stack Space

2️⃣ Tabulation (Bottom-Up Approach)

Code:

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

class Solution {
public:
    /* Function to count the number of LIS 
    present in the given array */
    int numberOfLIS(vector<int> nums) {
        int n = nums.size(); // Size of the array 

        int ans = 0; // To store the result
        int maxLen = 0; // To store the length of longest LIS

        vector<int> dp(n, 1); // DP table
        vector<int> count(n, 1); // To store the count

        // Filling up the DP table
        for(int ind = 0; ind < n; ind++) {
            for(int prevInd = 0; prevInd < ind; prevInd++) {

                /* If the element at index i can be
                included in the LIS ending at index j */
                if(nums[prevInd] < nums[ind]) {

                    // If a longer LIS is found, update the values
                    if(dp[prevInd] + 1 > dp[ind]) {
                        dp[ind] = dp[prevInd] + 1;
                        count[ind] = count[prevInd];
                    }

                    // Else if a new way is found to form the LIS
                    else if(dp[prevInd] + 1 == dp[ind]) {
                        count[ind] += count[prevInd];
                    }

                }
            }

            // Store the maximum length
            maxLen = max(maxLen, dp[ind]);
        }

        // Traverse the count array 
        for(int i = 0; i < n; i++) {
            // Count the longest LIS
            if(dp[i] == maxLen) ans += count[i];
        }

        return ans; // Return the result
    }
};


int main() {
    vector<int> arr = {1, 3, 5, 4, 7};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to count the number 
    of LIS present in given array */
    int ans = sol.numberOfLIS(arr);
    
    // Output
    cout << "The number of LIS present in the given array is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N^2), where N is the size of the given array.
  • Computing the DP array takes O(N^2) time, and counting the longest LIS present takes O(N) time.
• Space Complexity:O(N), because of two arrays (dp and count) used, each of size N.