Number of Longest Increasing Subsequences

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftGoogle

Given an array of integers, count how many distinct strictly increasing subsequences share the maximum possible length — not just what that longest length is, but how many different ways it can be reached. Extending the usual length table with a matching count table captures this directly: alongside dp[i], the length of the best increasing run ending at index i, keep how[i], the number of distinct subsequences that actually achieve that specific length at that index. Whenever an earlier, smaller element offers a strictly longer extension than anything found so far, index i's count resets to match that element's count, since a new best has been found. Whenever it only ties the current best length, that earlier element's count is folded in on top, because both routes are equally valid ways to reach the same length. Once every index carries its own length and count, the overall answer sums the counts of every index that reaches the longest length seen anywhere — since the true longest subsequence in the array may end at more than one position.

Test Case 1:

Input:nums = [2, 4, 6, 5, 8]

Output:2

Explanation:The longest increasing subsequences here have length 4: 2, 4, 6, 8 and 2, 4, 5, 8 — exactly 2 of them.

Test Case 2:

Input:nums = [6, 6, 6, 6, 6]

Output:5

Explanation:No element is strictly greater than another, so the longest increasing subsequence is just a single element — and any one of the 5 elements can be that single element, giving 5 ways.

Test Case 3:

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

Output:3

Explanation:The longest length is 5, reached three separate ways: 1,2,4,5,7 and 1,2,3,5,7 and 1,2,3,4,7 — each uses a different one of the middle three values (4, 3, or the second 4) before continuing on to 7.

Constraints

◆1 ≤ nums.length ≤ 12
◆-1000 ≤ nums[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Extend the plain skip/take LIS recursion so that, instead of returning just the best length reachable from here, every call returns a pair: the best length, and how many different ways that best length is achieved. At each index, both skipping it and (when the ordering allows) taking it get explored recursively, and each of those returns its own best-length/way-count pair. Whichever option reaches the greater length wins outright, contributing only its own way-count; but if the two options tie on length, both are equally valid, so their way-counts add together. Nothing here is cached, so the same sub-problem is re-solved, and re-counted, every time a different earlier choice happens to land on it again.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int findNumberOfLIS(int[] nums) {
        this.nums = nums;
        int[] result = solve(0, -1);
        return result[1];
    }

    private int[] solve(int i, int prev) {
        if (i == nums.length) return new int[]{0, 1};
        int[] skip = solve(i + 1, prev);
        int takeLen = -1, takeCount = 0;
        if (prev == -1 || nums[i] > nums[prev]) {
            int[] sub = solve(i + 1, i);
            takeLen = 1 + sub[0];
            takeCount = sub[1];
        }
        if (takeLen > skip[0]) return new int[]{takeLen, takeCount};
        if (takeLen == skip[0]) return new int[]{takeLen, takeCount + skip[1]};
        return skip;
    }
}

Optimal — Bottom-Up DP with Length and Count

Optimal

Keep two tables alongside each other: len[i], the length of the longest increasing subsequence ending exactly at index i (same as the plain LIS table), and cnt[i], how many distinct subsequences of that specific length end there. For every earlier index j with a smaller value, extending through j is possible. When that extension would make a strictly longer chain than anything seen for i so far, it becomes the new best, and i inherits j's way-count outright. When it only matches the current best length, j's way-count gets added on top, since both are equally valid routes to that same length. Once every index is filled in, the overall longest length is whatever the largest len[] value is, and the final answer sums cnt[i] over every index that actually reaches that length — since the true longest subsequence could end at more than one place.

TimeO(n²)