Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Number of Longest Increasing Subsequence

MEDIUMProblemSolveExternal Links

Description

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

A subsequence is a sequence that can be derived from the array by deleting zero or more elements without changing the order of the remaining elements. For example, [3, 6, 7] is a subsequence of [3, 5, 6, 2, 7].

An increasing subsequence is one where each element is strictly greater than the previous one.

Your task is not just to find the length of the longest increasing subsequence (LIS), but to count how many distinct increasing subsequences achieve that maximum length.

Examples

Example 1

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

Output: 2

Explanation: The length of the longest increasing subsequence is 4. There are exactly two increasing subsequences of length 4:

  • [1, 3, 5, 7] — picking indices 0, 1, 2, 4
  • [1, 3, 4, 7] — picking indices 0, 1, 3, 4

Both paths go through 1 → 3, then branch: one takes 5 (index 2) and the other takes 4 (index 3), before both converge on 7 (index 4). No increasing subsequence of length 5 exists, so the answer is 2.

Example 2

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

Output: 5

Explanation: Since the sequence must be strictly increasing, no two equal elements can appear in the same subsequence. The longest increasing subsequence has length 1 — each element by itself. There are 5 such subsequences (one per element), so the answer is 5.

Example 3

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

Output: 3

Explanation: The LIS length is 5. The three longest increasing subsequences are:

  • [1, 2, 4, 5, 7]
  • [1, 2, 3, 5, 7]
  • [1, 2, 3, 4, 7]

All have length 5, and no length-6 increasing subsequence exists.

Constraints

  • 1 ≤ nums.length ≤ 2000
  • -10^6 ≤ nums[i] ≤ 10^6
  • The answer is guaranteed to fit inside a 32-bit integer.

Editorial

Brute Force

Intuition

The most direct approach is to enumerate every possible increasing subsequence and count the ones with the maximum length.

Think of it like exploring every possible path through the array. At each element, you have a choice: include it in your current subsequence (if it's strictly greater than the last element you picked) or skip it. This naturally forms a recursion tree where each branch represents a different choice.

The plan is straightforward:

  1. First, explore all possible increasing subsequences to find the maximum length (the LIS length).
  2. Then, count how many increasing subsequences achieve that maximum length.

We split it into two passes because during exploration, we don't know the final LIS length in advance — a shorter subsequence found early might be surpassed by a longer one found later.

Step-by-Step Explanation

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

Pass 1 — Finding the LIS Length:

Step 1: Start with no elements chosen (prev = -∞, length = 0). We try including each element where nums[i] > prev.

Step 2: Pick nums[0] = 1 (1 > -∞). Now length = 1, prev = 1. From here, we can pick 3, 5, 4, or 7.

Step 3: Pick nums[1] = 3 (3 > 1). Length = 2, prev = 3. Can pick 5, 4, or 7.

Step 4: Pick nums[2] = 5 (5 > 3). Length = 3, prev = 5. Can only pick 7.

Step 5: Pick nums[4] = 7 (7 > 5). Length = 4, prev = 7. No more elements. Record maxLen = 4.

Step 6: Backtrack. From Step 3, skip 5 and try nums[3] = 4 (4 > 3). Length = 3, prev = 4.

Step 7: Pick nums[4] = 7 (7 > 4). Length = 4. Matches maxLen = 4.

Step 8: Many other branches are explored: {1, 5, 7}, {1, 4, 7}, {3, 5, 7}, {3, 4, 7}, etc. But none exceed length 4. After full exploration, maxLen = 4.

Pass 2 — Counting Subsequences of Length 4:

Step 9: Repeat the exploration, but now stop and count when length reaches 4.

Step 10: Path 1 → 3 → 5 → 7 reaches length 4. count = 1.

Step 11: Path 1 → 3 → 4 → 7 reaches length 4. count = 2.

Step 12: No other path reaches length 4.

Result: count = 2.

Algorithm

  1. Pass 1 — Find LIS length:

    • Use recursion to explore all increasing subsequences.
    • At each position, try extending with every future element that is strictly greater.
    • Track the maximum length reached across all paths.

  2. Pass 2 — Count LIS of that length:

    • Use the same recursive exploration.
    • When the current subsequence reaches the target length, increment a counter.
    • Prune branches that can't reach the target length (optional optimization).

  3. Return the counter.

Code

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;

        // Pass 1: Find the LIS length
        function<void(int, int, int)> findMax = [&](int idx, int prev, int len) {
            maxLen = max(maxLen, len);
            for (int i = idx; i < n; i++) {
                if (nums[i] > prev) {
                    findMax(i + 1, nums[i], len + 1);
                }
            }
        };
        findMax(0, INT_MIN, 0);

        // Pass 2: Count subsequences of length maxLen
        int count = 0;
        function<void(int, int, int)> countLIS = [&](int idx, int prev, int len) {
            if (len == maxLen) {
                count++;
                return;
            }
            for (int i = idx; i < n; i++) {
                if (nums[i] > prev) {
                    countLIS(i + 1, nums[i], len + 1);
                }
            }
        };
        countLIS(0, INT_MIN, 0);

        return count;
    }
};
class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        n = len(nums)

        # Pass 1: Find the LIS length
        max_len = [0]

        def find_max(idx, prev, length):
            max_len[0] = max(max_len[0], length)
            for i in range(idx, n):
                if nums[i] > prev:
                    find_max(i + 1, nums[i], length + 1)

        find_max(0, float('-inf'), 0)

        # Pass 2: Count subsequences of that length
        count = [0]

        def count_lis(idx, prev, length):
            if length == max_len[0]:
                count[0] += 1
                return
            for i in range(idx, n):
                if nums[i] > prev:
                    count_lis(i + 1, nums[i], length + 1)

        count_lis(0, float('-inf'), 0)
        return count[0]
class Solution {
    private int maxLen = 0;
    private int count = 0;

    public int findNumberOfLIS(int[] nums) {
        maxLen = 0;
        findMax(nums, 0, Integer.MIN_VALUE, 0);
        count = 0;
        countLIS(nums, 0, Integer.MIN_VALUE, 0);
        return count;
    }

    private void findMax(int[] nums, int idx, int prev, int len) {
        maxLen = Math.max(maxLen, len);
        for (int i = idx; i < nums.length; i++) {
            if (nums[i] > prev) {
                findMax(nums, i + 1, nums[i], len + 1);
            }
        }
    }

    private void countLIS(int[] nums, int idx, int prev, int len) {
        if (len == maxLen) {
            count++;
            return;
        }
        for (int i = idx; i < nums.length; i++) {
            if (nums[i] > prev) {
                countLIS(nums, i + 1, nums[i], len + 1);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

In the worst case (a strictly increasing array), every subset is an increasing subsequence. There are 2^n subsets, and for each we spend up to O(n) work traversing the array. This gives O(n × 2^n) total. Each pass has this cost, and we do two passes, but O(2 × n × 2^n) simplifies to O(n × 2^n).

Space Complexity: O(n)

The recursion stack depth is at most n (if we include every element). We use no additional data structures that grow with n.

Why This Approach Is Not Efficient

The brute force has exponential time complexity O(n × 2^n). With n up to 2000, this means roughly 2000 × 2^2000 operations — an astronomically large number that no computer could process in any reasonable time.

The fundamental problem is massive redundant computation. The recursion re-explores the same subproblems over and over. For example, when computing the LIS starting from index 5 with a previous value of 3, we perform the same recursive exploration regardless of how we arrived at that state (whether we came via index 1 → 5 or index 2 → 5).

The key insight: the length of the LIS ending at each index and the count of such subsequences depends only on the elements to its left — not on the full history of choices. This overlapping-subproblem structure is perfectly suited for dynamic programming.

Instead of generating all subsequences, we can compute two arrays in a single pass: lis[i] (the length of the LIS ending at index i) and count[i] (the number of such LIS ending at index i). This reduces the problem from exponential to polynomial time.

Bar chart comparing exponential brute force O(2^n) vs polynomial DP O(n²) for n=2000
Bar chart comparing exponential brute force O(2^n) vs polynomial DP O(n²) for n=2000

Optimal Approach - Dynamic Programming (Tabulation)

Intuition

This approach extends the classic Longest Increasing Subsequence (LIS) DP. In the standard LIS problem, we maintain an array lis[i] that stores the length of the longest increasing subsequence ending at index i. Here, we augment this with a second array count[i] that stores how many longest increasing subsequences of that length end at index i.

The recurrence works like this: for each element nums[i], we look at every previous element nums[j] where j < i and nums[j] < nums[i] (meaning we could extend a subsequence ending at j by appending nums[i]). Two cases arise:

  1. Longer chain found: If lis[j] + 1 > lis[i], we've discovered a strictly longer subsequence ending at i. We update lis[i] = lis[j] + 1 and replace the count: count[i] = count[j] (all previous paths to i at the old length are obsolete).

  2. Same-length path found: If lis[j] + 1 == lis[i], we've found another way to reach the same maximum length at i. We add to the count: count[i] += count[j] (accumulate paths).

Think of it like exploring a road network. Each intersection (index) can be reached by multiple routes. We track both the shortest distance (longest subsequence length) and the number of routes that achieve it. When we find a new shortcut, we reset the route count. When we find another route of the same optimal length, we add it to the total.

The final answer is the sum of count[i] for all indices where lis[i] equals the global maximum LIS length.

Step-by-Step Explanation

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

Step 1: Initialize. Every element alone forms an increasing subsequence of length 1, so lis = [1, 1, 1, 1, 1] and count = [1, 1, 1, 1, 1].

Step 2: Process i=1 (nums[1]=3). Check j=0: nums[0]=1 < 3. lis[0]+1=2 > lis[1]=1, so we found a longer chain. Update lis[1]=2, count[1]=count[0]=1. Subsequence: [1, 3].

  • lis = [1, 2, 1, 1, 1], count = [1, 1, 1, 1, 1]

Step 3: Process i=2 (nums[2]=5). Check j=0: nums[0]=1 < 5. lis[0]+1=2 > lis[2]=1 → lis[2]=2, count[2]=1. Then check j=1: nums[1]=3 < 5. lis[1]+1=3 > lis[2]=2 → even longer! Update lis[2]=3, count[2]=count[1]=1. Subsequence: [1, 3, 5].

  • lis = [1, 2, 3, 1, 1], count = [1, 1, 1, 1, 1]

Step 4: Process i=3 (nums[3]=4). Check j=0: 1 < 4, lis[0]+1=2 > 1 → lis[3]=2, count[3]=1. Check j=1: 3 < 4, lis[1]+1=3 > 2 → lis[3]=3, count[3]=count[1]=1. Check j=2: nums[2]=5 ≥ 4 — SKIP! 5 is NOT less than 4, so we can't extend the [1,3,5] subsequence with 4.

  • lis = [1, 2, 3, 3, 1], count = [1, 1, 1, 1, 1]

Step 5: Process i=4 (nums[4]=7). Check j=0: 1 < 7, lis[0]+1=2 > 1 → lis[4]=2, count[4]=1. Check j=1: 3 < 7, lis[1]+1=3 > 2 → lis[4]=3, count[4]=1.

Step 6: Continue i=4. Check j=2: nums[2]=5 < 7. lis[2]+1=4 > lis[4]=3 → new longest! lis[4]=4, count[4]=count[2]=1. This represents the path [1, 3, 5, 7].

Step 7 (KEY MOMENT): Check j=3: nums[3]=4 < 7. lis[3]+1=4 == lis[4]=4 → same length! count[4] += count[3] = 1+1 = 2. This represents a second path [1, 3, 4, 7] that achieves the same maximum length.

  • lis = [1, 2, 3, 3, 4], count = [1, 1, 1, 1, 2]

Step 8: All elements processed. maxLen = max(lis) = 4. Sum count[i] where lis[i]=4: only count[4]=2.

Result: 2.

Number of LIS — DP with Length and Count Tracking — Watch how we build two auxiliary arrays: lis[] tracks the longest subsequence length ending at each index, while count[] tracks how many subsequences achieve that length. The key insight is when two different paths yield the same length — we accumulate counts.

Algorithm

  1. Create two arrays of size n:

    • lis[i] = length of LIS ending at index i (initialize all to 1)
    • count[i] = number of LIS of length lis[i] ending at index i (initialize all to 1)

  2. For each index i from 1 to n-1:

    • For each index j from 0 to i-1:
      • If nums[j] < nums[i] (can extend):
        • If lis[j] + 1 > lis[i]: found a longer chain. Set lis[i] = lis[j] + 1 and count[i] = count[j].
        • Else if lis[j] + 1 == lis[i]: same-length path. Add count[i] += count[j].
    • Update global maxLen = max(maxLen, lis[i]).

  3. Sum all count[i] where lis[i] == maxLen. Return this sum.

Code

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        // lis[i] = length of longest increasing subseq ending at i
        // cnt[i] = number of such subsequences
        vector<int> lis(n, 1), cnt(n, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (lis[j] + 1 > lis[i]) {
                        // Found a strictly longer chain
                        lis[i] = lis[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (lis[j] + 1 == lis[i]) {
                        // Found another path of the same length
                        cnt[i] += cnt[j];
                    }
                }
            }
            maxLen = max(maxLen, lis[i]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] == maxLen) result += cnt[i];
        }
        return result;
    }
};
class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        # lis[i] = length of LIS ending at index i
        # count[i] = number of LIS of that length ending at i
        lis = [1] * n
        count = [1] * n
        max_len = 1

        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if lis[j] + 1 > lis[i]:
                        # Strictly longer chain found
                        lis[i] = lis[j] + 1
                        count[i] = count[j]
                    elif lis[j] + 1 == lis[i]:
                        # Another path of the same length
                        count[i] += count[j]
            max_len = max(max_len, lis[i])

        return sum(count[i] for i in range(n) if lis[i] == max_len)
import java.util.Arrays;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n];
        int[] count = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(count, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (lis[j] + 1 > lis[i]) {
                        lis[i] = lis[j] + 1;
                        count[i] = count[j];
                    } else if (lis[j] + 1 == lis[i]) {
                        count[i] += count[j];
                    }
                }
            }
            maxLen = Math.max(maxLen, lis[i]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] == maxLen) result += count[i];
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop iterates through each of the n elements. For each element i, the inner loop checks all j < i, giving at most i comparisons. The total number of comparisons is 0 + 1 + 2 + ... + (n-1) = n(n-1)/2, which is O(n²). Each comparison involves O(1) work (comparing values, updating lis and count). For n = 2000, this is about 2 × 10^6 operations — very fast.

Space Complexity: O(n)

We use two auxiliary arrays lis[] and count[], each of size n. No other data structures grow with input size. Total extra space: 2n integers = O(n).