keetcoder

# 673. Number of Longest Increasing Subsequence

LeetCode Problem Link (opens new window)

Given an unsorted array of integers, find the number of longest increasing subsequences.

Example 1:

  • Input: [1,3,5,4,7]
  • Output: 2
  • Explanation: There are two longest increasing subsequences, [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

  • Input: [2,2,2,2,2]
  • Output: 5
  • Explanation: The longest increasing subsequence length is 1, and there are 5 subsequences of length 1, so output 5.

# Approach

This problem can be considered as an advanced version of 0300.Longest Increasing Subsequence (opens new window).

  1. Define the dp array (dp table) and the meaning of indices

For this problem, we maintain two arrays together.

dp[i]: The length of the longest increasing subsequence up to and including index i is dp[i].

count[i]: The number of the longest increasing subsequences ending with nums[i] is count[i].

  1. Define the transition formula

In the problem of 0300. Longest Increasing Subsequence, we established the state transition as:

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
1

That is: the length of the longest increasing subsequence for position i is equal to the maximum value of j from 0 to i-1 using their longest increasing subsequences plus one.

This problem is more complex, as we need to consider two dimensions: updating dp[i] and updating count[i].

How do we update count[i]?

Given a sequence ending with nums[i], the number of the longest increasing subsequences is count[i].

Thus, given nums[i] > nums[j], if within range [0, i-1], we find j such that dp[j] + 1 > dp[i], it indicates we found a longer increasing subsequence. Therefore, the number of longest increasing subsequences ending with j is the latest count of the longest increasing subsequences ending with i, i.e., count[i] = count[j].

Given nums[i] > nums[j], if within range [0, i-1], we find j such that dp[j] + 1 == dp[i], it implies there are two increasing subsequences of the same length. Thus, the number of longest increasing subsequences ending with i should be increased by the number of longest increasing subsequences ending with j, i.e., count[i] += count[j].

The code is as follows:

if (nums[i] > nums[j]) {
    if (dp[j] + 1 > dp[i]) {
        count[i] = count[j];
    } else if (dp[j] + 1 == dp[i]) {
        count[i] += count[j];
    }
    dp[i] = max(dp[i], dp[j] + 1);
}
1
2
3
4
5
6
7
8

You can also write it like this:

if (nums[i] > nums[j]) {
    if (dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1; // Update dp[i] here, no need for max anymore
        count[i] = count[j];
    } else if (dp[j] + 1 == dp[i]) {
        count[i] += count[j];
    }
}
1
2
3
4
5
6
7
8

Here count[i] records the number of longest increasing subsequences ending with nums[i]. dp[i] tracks the length of the longest increasing subsequence up to i (inclusive).

To find the number of longest increasing subsequences, we should keep a record of the maximum length.

The code is:

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            if (dp[j] + 1 > dp[i]) {
                count[i] = count[j];
            } else if (dp[j] + 1 == dp[i]) {
                count[i] += count[j];
            }
            dp[i] = max(dp[i], dp[j] + 1);
        }
        if (dp[i] > maxCount) maxCount = dp[i]; // Record the max length
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  1. Initialize the dp array

Review the definitions of dp[i] and count[i].

count[i] records the number of the longest increasing subsequences ending with nums[i].

At the minimum, this is 1, so initialize count[i] to 1.

dp[i] records the length of the longest increasing sequence up to and including i.

The minimum length is also 1, so initialize dp[i] to 1.

The code is:

vector<int> dp(nums.size(), 1);
vector<int> count(nums.size(), 1);
1
2

Initialization in dynamic programming problems is very crucial and tests the understanding of the dp array's definition.

  1. Determine the traversal order

dp[i] is derived from the longest increasing subsequence of each position from 0 to i-1, so we must traverse i from front to back.

j traverses from 0 to i-1, with i as the outer loop and j as the inner loop. Code is:

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            if (dp[j] + 1 > dp[i]) {
                count[i] = count[j];
            } else if (dp[j] + 1 == dp[i]) {
                count[i] += count[j];
            }
            dp[i] = max(dp[i], dp[j] + 1);
        }
        if (dp[i] > maxCount) maxCount = dp[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Finally, traverse dp[i] again. Accumulate count[i] that corresponds to the length of the longest increasing sequence, which is the result.

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            if (dp[j] + 1 > dp[i]) {
                count[i] = count[j];
            } else if (dp[j] + 1 == dp[i]) {
                count[i] += count[j];
            }
            dp[i] = max(dp[i], dp[j] + 1);
        }
        if (dp[i] > maxCount) maxCount = dp[i];
    }
}
int result = 0; // Gather the result
for (int i = 0; i < nums.size(); i++) {
    if (maxCount == dp[i]) result += count[i];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Revisit dp[i] and count[i] definition if the calculation seemed confusing.

  1. Example walkthrough of the dp array

Input: [1,3,5,4,7]

673. Number of Longest Increasing Subsequence

If the code doesn't work no matter what you try, print the dp and count arrays to check if they are correct!

Analysis complete, here is the full C++ code:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        vector<int> count(nums.size(), 1);
        int maxCount = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
                if (dp[i] > maxCount) maxCount = dp[i];
            }
        }
        int result = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

There is also an O(n log n) solution using a Fenwick tree. I am busy today and won’t write it up, but interested students can learn about it themselves here: Here are the Fenwick tree series blogs I wrote earlier (opens new window) (Decade-old archived texts).

# Other Language Versions

# Java

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        for(int i = 0; i < dp.length; i++) dp[i] = 1;
        int[] count = new int[nums.length];
        for(int i = 0; i < count.length; i++) count[i] = 1;

        int maxCount = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
                if (dp[i] > maxCount) maxCount = dp[i];
            }
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# Python

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        if size<= 1: return size

        dp = [1 for i in range(size)]
        count = [1 for i in range(size)]

        maxCount = 0
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i] :
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i] :
                        count[i] += count[j]
                if dp[i] > maxCount:
                    maxCount = dp[i];
        result = 0
        for i in range(size):
            if maxCount == dp[i]:
                result += count[i]
        return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Go

func findNumberOfLIS(nums []int) int {
	size := len(nums)
	if size <= 1  {
		return size
	}

	dp := make([]int, size);
	for i, _ := range dp {
		dp[i] = 1
	}
	count := make([]int, size);
	for i, _ := range count {
		count[i] = 1
	}

	maxCount := 0
	for i := 1; i < size; i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				if dp[j] + 1 > dp[i] {
					dp[i] = dp[j] + 1
					count[i] = count[j]
				} else if dp[j] + 1 == dp[i] {
					count[i] += count[j]
				}
			}
			if dp[i] > maxCount {
				maxCount = dp[i]
			}
		}
	}

	result := 0
	for i := 0; i < size; i++ {
		if maxCount == dp[i] {
			result += count[i]
		}
	}
	return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# JavaScript

var findNumberOfLIS = function(nums) {
    const len = nums.length;
    if(len <= 1) return len;
    let dp = new Array(len).fill(1); // The longest increasing subsequence up to and including i is dp[i]
    let count = new Array(len).fill(1); // The number of the longest increasing subsequences ending with nums[i]
    let res = 0;
    for(let i = 1; i < len; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                if(dp[j] + 1 > dp[i]){ // Sequence length with nums[j] as the previous element could be longer
                    dp[i] = dp[j] + 1; // Update dp[i] 
                    count[i] = count[j]; // Reset count[i]
                } else if(dp[j] + 1 === dp[i]){ // Equal to existing length
                    count[i] += count[j]; // Update count[i]
                }
            }
        }
    }
    let max = Math.max(...dp); // Spread operator to find maximum length
    for(let i = 0; i < len; i++) if(dp[i] === max) res += count[i]; // Accumulate
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Last updated:: 9/4/2025, 3:19:38 PM
Copyright © 2025 keetcoder