Number of Longest Increasing Subsequence
Understanding the Problem
This problem extends the classic Longest Increasing Subsequence (LIS) problem. Instead of finding the length of the LIS, we 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 complication is that we have to track two quantities at every position, not one: the length of the longest increasing subsequence ending there, and the number of distinct subsequences that reach that length. Finding the maximum length alone is the standard LIS problem. Counting requires propagating the second quantity correctly as longer subsequences are built.
Key Constraints:
1 <= nums.length <= 2000--> With n up to 2000, an O(n^2) solution runs about 4 million operations and passes comfortably. O(n^3) would be 8 billion, which is too slow.-10^6 <= nums[i] <= 10^6--> Values can be negative and span a wide range, so a value-indexed array is not practical. We compare values directly, and if we want a value-indexed structure we coordinate-compress first.
Approach 1: Brute Force (Generate All Subsequences)
Intuition
Generate every increasing subsequence, find the maximum length among them, and count how many reach that maximum. Recursion (backtracking) enumerates all of them: at each index, either include the current element (when it is greater than the last included element) or skip it.
This is correct but generates an exponential number of subsequences, so it only works for small inputs. The counting logic in the faster approaches follows the same two branches seen here: a longer subsequence resets the best length, an equal-length one adds to the count.
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
Trace nums = [1, 3, 5, 4, 7]. The recursion starts with lastVal = -infinity and currentLen = 0, then branches on each index.
Each distinct increasing subsequence corresponds to exactly one path through the recursion, because every path picks a fixed set of indices in order. The two paths that reach length 4 are:
- 1, 3, 5, 7. The first to reach length 4, so
maxLenbecomes 4 andcountbecomes 1. - 1, 3, 4, 7. Also length 4, so
currentLen == maxLenandcountincrements to 2.
Every other path produces a subsequence of length 3 or less (for example 1, 3, 5 or 3, 4, 7), so none of them affect count once maxLen is 4. After the full recursion, count is 2, which is the answer.
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).
The exponential cost comes from recomputing the same suffixes repeatedly. The next approach computes the LIS length and count ending at each index once and reuses earlier results.
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.
Setting cnt[i] = cnt[j] means every length-length[j] subsequence ending at j extends to a longer one ending at i by appending nums[i]. Adding cnt[j] to cnt[i] records additional subsequences that reach the same length through a different predecessor j. No subsequence is double-counted, because each one has a unique predecessor j (the index of its second-to-last element).
The argument relies on processing indices left to right. When index i is computed, every predecessor j < i already holds its final length[j] and cnt[j], so the values read for i are complete.
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 is fast enough for n <= 2000. For larger inputs, the O(n) inner scan of predecessors becomes the bottleneck. The next approach replaces that scan with an O(log n) 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.
Processing left to right keeps the same invariant as the DP: when nums[i] is processed, the tree holds the best (length, count) for every value already seen. Querying the range of ranks [1, rank(nums[i]) - 1] returns the best subsequence among all strictly smaller values, which is exactly the set of valid predecessors.
The merge defines how two range results combine: keep the longer length, and when two ranges tie on length, sum their counts. This matches the two branches of the DP (a longer predecessor replaces, an equal-length one accumulates), so the count stays correct while the inner scan drops from O(n) to O(log n).
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.