Number of Longest Increasing Subsequence

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.