Number of Longest Increasing Subsequence
Count how many strictly increasing subsequences have the maximum length, by tracking for each index both the longest length ending there and how many ways reach it.
Problem Understanding
Number of Longest Increasing Subsequence: given an integer array nums, return the number of longest strictly increasing subsequences.
Examples: [1,3,5,4,7] → 2 ([1,3,4,7] and [1,3,5,7]); [2,2,2,2,2] → 5.
The Intuition: Longest Increasing Subsequence, Plus a Counter
Start from Longest Increasing Subsequence: length[i] is the longest increasing subsequence ending at i. Now also count:
- Strictly longer via j: take the new length and replace the count with
count[j]. - Same length via j: add
count[j], more ways to the same best. - Finish: add up
count[i]whereverlength[i]is the overall maximum.
The same "count the ways to reach the optimum" trick appears in many dynamic programming problems.
Interactive Walkthrough
len = LONGEST ENDING HERE · cnt = HOW MANY REACH IT
len = cnt = 1
nums
len
cnt
longest
1
answer
:
Every element alone is an increasing subsequence: len = 1, cnt = 1 everywhere
Next
1 < 3: extending gives length 2, longer than before. len[1] = 2, cnt[1] = cnt[0] = 1
nums
Rows show nums, length and count. Index i is filled, the earlier j is marked, and the cells a step changed are highlighted. Try Three ways to see counts add up.
Dry Run Table
Input: [1,3,5,4,7].
| i | nums[i] | length | count |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 3 | 2 | 1 |
| 2 | 5 | 3 | 1 |
| 3 | 4 | 3 | 1 |
| 4 | 7 | 4 | 2 (via 5 and via 4) |
Answer: 2.
The Solution Template
Two arrays, one double loop.
Number of Longest Increasing Subsequence Code
1var findNumberOfLIS = function(nums) {2 const n = nums.length;3 const length = new Array(n).fill(1), count = new Array(n).fill(1);4 for (let i = 0; i < n; i++) {5 for (let j = 0; j < i; j++) {6 if (nums[j] >= nums[i]) continue;7 if (length[j] + 1 > length[i]) {8 length[i] = length[j] + 1;9 count[i] = count[j];10 } else if (length[j] + 1 === length[i]) {11 count[i] += count[j];12 }13 }14 }15 const longest = Math.max(...length);16 let total = 0;17 for (let i = 0; i < n; i++) if (length[i] === longest) total += count[i];18 return total;19};
Edge Cases & Common Mistakes
- All equal values: every element alone is a longest subsequence; the answer is n.
- Strictly increasing only: use
<, not<=. - Adding instead of replacing on a longer length: keeps counts of shorter subsequences.
- Returning count of the last index: the longest subsequences can end anywhere.
- Single element: answer 1.
Summary
Track length[i] and count[i]; a longer extension replaces the count, an equal one adds to it; sum count[i] where length[i] is the maximum. O(n²) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet