DSA problem
Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest strictly increasing subsequences. A subsequence is obtained by deleting zero or more elements without changing the relative order of the remaining elements.
This problem extends the classic LIS task: instead of merely reporting the length of the longest increasing subsequence, you also need to count how many distinct subsequences achieve that length. Two distinct subsequences are counted as different even if they contain the same multiset of values, as long as they come from different index choices.
The natural way to track both quantities is to carry two parallel arrays during the DP. Let dp[i] denote the length of the longest increasing subsequence ending exactly at index i, and let count[i] denote how many such longest-at-i subsequences exist. Both start at 1 for every index because the single-element subsequence [nums[i]] always exists.
For every pair j < i with nums[j] < nums[i], the subsequence ending at j can be extended by appending nums[i]. If dp[j] + 1 > dp[i] we have discovered a strictly longer subsequence ending at i, so we reset dp[i] = dp[j] + 1 and adopt count[i] = count[j]. If dp[j] + 1 == dp[i] we have found another way to reach the same best length, so we accumulate count[i] += count[j]. After filling both arrays, find the global maximum length L and sum count[i] across every index where dp[i] == L. The total runs in O(n²) time and O(n) space.
Examples
nums = [1,3,5,4,7]2nums = [2,2,2,2,2]5nums = [1,2,4,3,5,4,7,2]3Constraints
- 1 <= nums.length <= 2000
- -10^6 <= nums[i] <= 10^6
- The subsequence must be strictly increasing.
- O(n²) time is expected.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.