Number of Longest Increasing Subsequence
Last Updated: March 28, 2026
Understanding the Problem
This problem builds on the classic Longest Increasing Subsequence (LIS) problem, but with a twist. Instead of just finding the length of the LIS, we need to count how many subsequences achieve that maximum length.
A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements. "Strictly increasing" means each element must be larger than the previous one (not equal).
The key challenge here is that we are not just tracking one thing (the longest length), but two things simultaneously: the length of the longest increasing subsequence ending at each position, and the number of ways to achieve that length. This dual-tracking is what makes the problem interesting. If you can solve standard LIS, you are halfway there. The other half is maintaining counts correctly as you build longer subsequences.
Key Constraints:
1 <= nums.length <= 2000--> With n up to 2000, O(n^2) means at most 4 million operations, which is perfectly fine. O(n^3) would be 8 billion, which is too slow.-10^6 <= nums[i] <= 10^6--> Values can be negative, so we cannot use value-indexed arrays. The large value range means we need comparison-based approaches.
Approach 1: Brute Force (Generate All Subsequences)
Intuition
The most direct way to solve this is to generate every possible increasing subsequence, find the maximum length among them, and count how many hit that maximum. We can use recursion (backtracking) to enumerate all subsequences: at each index, we either include the current element (if it is greater than the last included element) or skip it.
This works correctly but generates an exponential number of subsequences, which makes it impractical for anything beyond tiny inputs.
Algorithm
- Use a recursive function that takes the current index and the last chosen element.
- At each index, try two choices: skip the element, or include it (if it is greater than the last chosen element).
- Track the length of each complete subsequence.
- After exploring all subsequences, find the maximum length and count how many subsequences have that length.
Example Walkthrough
For nums = [1, 3, 5, 4, 7], the recursion explores all valid increasing subsequences. It finds two subsequences of maximum length 4: [1, 3, 5, 7] and [1, 3, 4, 7]. So the answer is 2.
Code
- Time Complexity: O(2^n). In the worst case (a strictly increasing array), every subset is a valid increasing subsequence. There are 2^n subsets, and we explore all of them.
- Space Complexity: O(n). The recursion depth is at most n (one call per element in the longest path).
This approach works correctly but is exponentially slow. What if we computed the LIS length and count ending at each index just once, reusing results from earlier indices?
Approach 2: Dynamic Programming
Intuition
The standard LIS DP approach computes, for each index i, the length of the longest increasing subsequence ending at i. We do this by looking at every earlier index j where nums[j] < nums[i] and taking the maximum length[j] + 1.
To count the number of LIS, we add a second array cnt alongside the length array. cnt[i] tracks how many increasing subsequences of length length[i] end at index i. When we examine a pair (j, i) where nums[j] < nums[i], there are three cases:
- If
length[j] + 1 > length[i]: we found a longer subsequence ending ati. Updatelength[i]and resetcnt[i] = cnt[j]. - If
length[j] + 1 == length[i]: we found another set of subsequences with the same max length ending ati. Addcnt[j]tocnt[i]. - If
length[j] + 1 < length[i]: this path is shorter than what we already have. Ignore it.
After filling both arrays, find the maximum value in length, then sum up cnt[i] for every index where length[i] equals that maximum.
The count propagates correctly because of how we build subsequences. When we set cnt[i] = cnt[j], we are saying "every way to build a LIS of length length[j] ending at j can be extended by appending nums[i]." When we add cnt[j] to cnt[i], we are saying "here are additional ways to reach the same length through a different predecessor." By the time we finish processing index i, cnt[i] holds the total number of distinct increasing subsequences of length length[i] that end at position i.
This works because DP processes indices left to right, so when we compute values for index i, all predecessors j < i already have their final length and cnt values.
Algorithm
- Initialize two arrays:
length[i] = 1andcnt[i] = 1for alli(each element by itself is a subsequence of length 1, and there is exactly one such subsequence). - For each index
ifrom 1 to n-1, scan all previous indicesjfrom 0 to i-1. - If
nums[j] < nums[i]: - If
length[j] + 1 > length[i]: setlength[i] = length[j] + 1andcnt[i] = cnt[j]. - If
length[j] + 1 == length[i]: addcnt[j]tocnt[i]. - Track the overall maximum length
maxLenas you go. - Sum
cnt[i]for all indices wherelength[i] == maxLen. Return that sum.
Example Walkthrough
Code
- Time Complexity: O(n^2). The outer loop runs n times, and for each iteration, the inner loop runs up to i times. Total comparisons: n*(n-1)/2, which is O(n^2).
- Space Complexity: O(n). We use two arrays of size n (
lengthandcnt), plus a few variables.
This DP approach is efficient enough for n <= 2000. But what if we needed to handle larger inputs? We can replace the linear scan of predecessors with a segment tree query.
Approach 3: Segment Tree
Intuition
The O(n^2) approach spends O(n) time per element querying all predecessors. We can speed this up by framing the query differently: for each nums[i], we want the maximum LIS length (and the count of subsequences achieving that length) among all elements with value strictly less than nums[i].
This is a range-max query, which a segment tree handles in O(log n). We coordinate-compress the values, build a segment tree over the compressed values, and for each element, query then update.
Each node in the segment tree stores a pair (maxLength, count): the longest LIS length among subsequences ending with a value in that range, and the total number of such subsequences.
The segment tree stores the best (length, count) pair for each possible value in the compressed range. When processing nums[i], querying [1, rank(nums[i])-1] gives us the best LIS information among all values strictly less than nums[i] that we have processed so far. The merge operation correctly combines results: if two ranges have the same max length, we sum their counts. If one is longer, we take the longer one.
This transforms the O(n) inner scan of the DP approach into an O(log n) query, while maintaining the same correctness guarantees.
Algorithm
- Coordinate-compress the values in
numsto map them to the range [1, m] where m is the number of distinct values. - Build a segment tree over the range [1, m], where each node stores
(maxLength, count), initialized to(0, 0). - For each element
nums[i](left to right): - Query the segment tree for the range [1, compressed(nums[i]) - 1] to get the best
(prevLen, prevCnt)among all smaller values. - Set
newLen = prevLen + 1. IfprevLen == 0, setnewCnt = 1. Otherwise,newCnt = prevCnt. - Update the segment tree at position
compressed(nums[i])by merging(newLen, newCnt)with whatever is already stored there. - Query the full range [1, m] for the final answer. The count in the result is the answer.
Example Walkthrough
For nums = [1, 3, 5, 4, 7] with compressed ranks {1:1, 3:2, 4:3, 5:4, 7:5}:
- Process 1 (rank 1): query [1,0] returns (0,0), insert (1,1) at rank 1.
- Process 3 (rank 2): query [1,1] returns (1,1), insert (2,1) at rank 2.
- Process 5 (rank 4): query [1,3] returns (2,1), insert (3,1) at rank 4.
- Process 4 (rank 3): query [1,2] returns (2,1), insert (3,1) at rank 3.
- Process 7 (rank 5): query [1,4] returns (3,2) since both rank 3 and rank 4 have length 3. Insert (4,2) at rank 5.
- Final query [1,5] returns (4,2). Answer: 2.
Code
- Time Complexity: O(n log n). We process each element once, and each query/update on the segment tree takes O(log m) time where m <= n is the number of distinct values.
- Space Complexity: O(n). The segment tree uses O(m) space where m <= n, plus O(n) for the rank mapping.