DSA
Number of Longest Increasing Subsequence
Time O(n^2), Space O(n).
Key insighttry it first, then reveal
This builds directly on top of Longest Increasing Subsequence — same O(n^2) DP shape, but tracking one extra piece of information per index.
Practice Link
Given an integer array nums, return the number of longest increasing subsequences. Notice that the subsequence must be strictly increasing.
Intuition#
This builds directly on top of Longest Increasing Subsequence — same O(n^2) DP shape, but tracking one extra piece of information per index.
lis[i] = length of the longest increasing subsequence ending at index i, computed the usual way: for every j < i with nums[j] < nums[i], lis[i] = max(lis[i], 1 + lis[j]).
The part that's easy to get wrong is the counting. It's not enough to count how many indices i achieve the overall max length — a single index can be the endpoint of several distinct maximum-length subsequences (multiple j's tying for the best extension into it), and that has to be tracked while building lis, not reconstructed afterward.
So alongside lis[i], maintain count[i] = number of distinct LIS's of length lis[i] ending at index i, both initialized to 1 (every element is trivially a subsequence of length 1, in exactly one way). While scanning j < i with nums[j] < nums[i]:
- If lis[j] + 1 > lis[i]: we've found a strictly longer path into i, so count[i] resets to count[j] — the old ways of reaching lis[i] are no longer the longest.
- If lis[j] + 1 == lis[i]: j offers another, equally long way to reach i, so count[i] += count[j] — accumulate, don't overwrite.
Finally, the overall answer sums count[i] over every i whose lis[i] equals the global longest — because the longest subsequence can legitimately end at more than one index.
Solution#
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
int maxi=0;
vector<int> lis(n, 1);
vector<int> count(n,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(nums[j] < nums[i]){
if(lis[j]+1 > lis[i]){
lis[i] = 1 + lis[j];
count[i] = count[j];
}else if(lis[j]+1 == lis[i])
count[i] += count[j];
}
}
maxi = max(maxi, lis[i]);
}
int cnt = 0;
for(int i=0;i<n;i++){
if(lis[i] == maxi)
cnt += count[i];
}
return cnt;
}
};
Complexities#
Time Complexity: O(n^2) — nested loop over all pairs (i, j).
Space Complexity: O(n) for the lis and count arrays.