Log inSign up
mediumLeetCodeNot Started

Number of Longest Increasing Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

### Example 1 - Input: nums = [1, 3, 5, 4, 7] - Output: 2 - Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7] (both length 4).

### Example 2 - Input: nums = [2, 2, 2, 2, 2] - Output: 5 - Explanation: The length of the longest increasing subsequence is 1, and there are 5 subsequences of length 1 (each individual element), so output 5.

Constraints:

  • 1 <= nums.length <= 2000
  • -106 <= nums[i] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the technique of tracking path counts alongside optimal DP values.
  • Handle ties and resets in combinatorial dynamic programming.
  • Sum over all endpoints matching the global optimum.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Increasing subsequence problem.
  • Asked for COUNT of optimal solutions rather than just max length/sum.

Algorithmic Decision Tree:

  • Maintain dual states (optimal value, frequency of optimal value).
  • Reset count on strictly better length, accumulate count on tied length.

Connected Patterns:

Longest Increasing SubsequenceMaximum Sum Increasing Subsequence

1. Recursive Subsequence Generation

Intuition

Generate all 2n subsequences, filter for strictly increasing order, find max length, and count them.

Algorithm

  1. Generate all subsets of indices.
  2. Verify if values are strictly increasing.
  3. Record max length and maintain a frequency map.
  4. Return the count corresponding to the maximum length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 void dfs(int idx, vector<int>& current, const vector<int>& nums, int& maxLen, int& count) {
9 if (idx == nums.size()) {
10 if (current.size() > maxLen) {
11 maxLen = current.size();
12 count = 1;
13 } else if (current.size() == maxLen && maxLen > 0) {
14 count++;
15 }
16 return;
17 }
18 // Exclude
19 dfs(idx + 1, current, nums, maxLen, count);
20 // Include
21 if (current.empty() || nums[idx] > current.back()) {
22 current.push_back(nums[idx]);
23 dfs(idx + 1, current, nums, maxLen, count);
24 current.pop_back();
25 }
26 }
27public:
28 int findNumberOfLIS(vector<int>& nums) {
29 if (nums.empty()) return 0;
30 int maxLen = 0, count = 0;
31 vector<int> current;
32 dfs(0, current, nums, maxLen, count);
33 return count;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 3, 5, 4, 7};
40 cout << "Number of LIS: " << sol.findNumberOfLIS(nums) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^n * n)
  • Space complexity: O(n)

2. Memoized Top-Down DP with Path Counts

Intuition

Memoize a pair (max_len, count) for state (idx, prevIdx).

Algorithm

  1. Define memo table returning pair {len, count}.
  2. Combine child states by taking max length and summing counts on ties.
  3. Return global count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <utility>
4
5using namespace std;
6
7class Solution {
8public:
9 int findNumberOfLIS(vector<int>& nums) {
10 int n = nums.size();
11 if (n <= 1) return n;
12
13 vector<int> len(n, 1), count(n, 1);
14 int maxLen = 1;
15
16 for (int i = 0; i < n; ++i) {
17 for (int j = 0; j < i; ++j) {
18 if (nums[j] < nums[i]) {
19 if (len[j] + 1 > len[i]) {
20 len[i] = len[j] + 1;
21 count[i] = count[j];
22 } else if (len[j] + 1 == len[i]) {
23 count[i] += count[j];
24 }
25 }
26 }
27 maxLen = max(maxLen, len[i]);
28 }
29
30 int ans = 0;
31 for (int i = 0; i < n; ++i) {
32 if (len[i] == maxLen) ans += count[i];
33 }
34 return ans;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> nums = {1, 3, 5, 4, 7};
41 cout << "Number of LIS: " << sol.findNumberOfLIS(nums) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

3. Dual-Array 1D Tabulation (O(n^2) Time, O(n) Space)

Intuition

Track both max lengths and occurrence counts with two parallel arrays len and count, updating in a single pass.

Algorithm

  1. Initialize len array of size n with 1.
  2. Initialize count array of size n with 1.
  3. Track maxLen = 1.
  4. For i from 0 to n - 1:
  5. For j from 0 to i - 1:
  6. If nums[j] < nums[i]:
  7. If len[j] + 1 > len[i]: len[i] = len[j] + 1, count[i] = count[j].
  8. Else if len[j] + 1 == len[i]: count[i] += count[j].
  9. maxLen = max(maxLen, len[i]).
  10. Sum count[i] for all i where len[i] == maxLen.
  11. Return the sum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findNumberOfLIS(vector<int>& nums) {
10 int n = nums.size();
11 if (n <= 1) return n;
12
13 vector<int> len(n, 1);
14 vector<int> count(n, 1);
15 int maxLen = 1;
16
17 for (int i = 0; i < n; ++i) {
18 for (int j = 0; j < i; ++j) {
19 if (nums[j] < nums[i]) {
20 if (len[j] + 1 > len[i]) {
21 len[i] = len[j] + 1;
22 count[i] = count[j];
23 } else if (len[j] + 1 == len[i]) {
24 count[i] += count[j];
25 }
26 }
27 }
28 maxLen = max(maxLen, len[i]);
29 }
30
31 int totalCount = 0;
32 for (int i = 0; i < n; ++i) {
33 if (len[i] == maxLen) {
34 totalCount += count[i];
35 }
36 }
37
38 return totalCount;
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<int> nums = {1, 3, 5, 4, 7};
45 cout << "Number of LIS: " << sol.findNumberOfLIS(nums) << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive GenerationO(2^n * n)O(n)Exhaustive branching over subsets, filtering increasing sequences.2n subsets
2.Top-Down Pair MemoizationO(n^2)O(n^2)Memoize (length, count) pairs.Table allocation and recursion overhead
3.Dual-Array 1D TabulationOptimalO(n^2)O(n)Parallel len[i] and count[i] arrays updated in a single pass.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to reset count[i] = count[j] when a strictly longer sequence is discovered (len[j] + 1 > len[i]).

Pitfall 2:

Returning count[n - 1] instead of summing count[i] over all indices i that achieve maxLen.

Crucial Edge Cases to Validate:

  • All elements identical: e.g. [2, 2, 2]. Max length is 1, and count is n.
  • Strictly decreasing array: Max length is 1, count is n.
  • Single element: Length 1, count 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast this with standard LIS: in standard LIS we can use binary search / patience sorting in O(n log n), but here because we need counts of all paths, the dual-array DP O(n2) or a Segment Tree with coordinate compression in O(n log n) is required.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When we find that len[j] + 1 == len[i], why do we add count[j] to count[i] instead of overwriting it?

Back to DSA Sheet