Number of Longest Increasing Subsequence

Number of Longest Increasing Subsequence: 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].

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 increasing subsequences of length 1, so output 5.

Constraints:

1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public int findNumberOfLIS(int[] nums) {
    int n = nums.length, totalCount = 0, maxLength = 0;

    int[] lengths =  new int[n], counts = new int[n];

    for(int i = 0; i < n; ++i){
        lengths[i] = 1;
        counts[i] = 1;

        for(int j = 0; j < i; ++j){
            if(nums[j] < nums[i]){
                if(lengths[i] == lengths[j] + 1){
                    counts[i] += counts[j];
                }
                if(lengths[i] < lengths[j] + 1){
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                }
            }
        }
        if(maxLength == lengths[i]){
            totalCount += counts[i];
        }
        if(maxLength < lengths[i]){
            maxLength = lengths[i];
            totalCount = counts[i];
        }
    }
    return totalCount;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
  const n = nums.length;
  let totalCount = 0;
  let maxLength = 0;

  const lengths = new Array(n).fill(1);
  const counts = new Array(n).fill(1);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        if (lengths[i] === lengths[j] + 1) {
          counts[i] += counts[j];
        }
        if (lengths[i] < lengths[j] + 1) {
          lengths[i] = lengths[j] + 1;
          counts[i] = counts[j];
        }
      }
    }
    if (maxLength === lengths[i]) {
      totalCount += counts[i];
    }
    if (maxLength < lengths[i]) {
      maxLength = lengths[i];
      totalCount = counts[i];
    }
  }
  return totalCount;
};

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        totalCount = 0
        maxLength = 0

        lengths = [1] * n
        counts = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if lengths[i] == lengths[j] + 1:
                        counts[i] += counts[j]
                    if lengths[i] < lengths[j] + 1:
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
            if maxLength == lengths[i]:
                totalCount += counts[i]
            if maxLength < lengths[i]:
                maxLength = lengths[i]
                totalCount = counts[i]
        return totalCount

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        int totalCount = 0;
        int maxLength = 0;

        std::vector<int> lengths(n, 1);
        std::vector<int> counts(n, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (lengths[i] == lengths[j] + 1) {
                        counts[i] += counts[j];
                    }
                    if (lengths[i] < lengths[j] + 1) {
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    }
                }
            }
            if (maxLength == lengths[i]) {
                totalCount += counts[i];
            }
            if (maxLength < lengths[i]) {
                maxLength = lengths[i];
                totalCount = counts[i];
            }
        }
        return totalCount;
    }
};

Time/Space Complexity:

Time Complexity: O(n^2)
Space Complexity: O(n)

Explanation:

So, we have two arrays lengths (tracks the max length of subsequence ending with element i as lengths[i]) and counts (tracks the count of subsequences of length length[i] ending with element i). The algorithm works as follows:

We have a base case where each element is a strictly increasing subsequence of length 1
We iterate over each of the subsequences with two loops (each time j goes up to i)
For each element in the array we try to form the largest strictly increasing subsequence with the element that came before it, so we compare it with each nums[j]
if nums[j] < nums[i] that means that elements at indices i and j can form an increasing subsequence
Now we have two subcases, the first one is when we have length of sequence ending at i just by one element longer than max sequence ending in j which means we can combine every sequence of length length[j] with the element at index i to form a longer sequence, so we add the count[j] (number of sequences of length length[j] ending at j). The second case is when we have a longer sequence in j, which means adding element at index i will just increase it by one, and the total count of those sequence ending at i will be the same as total count of sequence of length[j] ending at j
The last two “if” statements update the count of maximum length subsequence (while also keeping track of how long that sequence is)
Again we have two cases, first one if the maximum length sequence so far is of the same length as sequence(s) ending at i which means we can just increment our total counter by counts[i], otherwise we found a longer sequence ending at i and we have to update the maxLength and reset the total count to be equal to the number of sequences of length[i] ending at index i which is counts[i].

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​