Number of Longest Increasing Subsequence

Problem

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

Notice that the sequence has to be strictly increasing.

Examples

Example 1:

1
2
3


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:

1
2
3


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

Solution

Method 1 – Dynamic Programming

Intuition

We want to find not just the length of the longest increasing subsequence (LIS), but also how many such sequences exist. For each position, we track both the length of the LIS ending there and the number of ways to achieve that length. By updating these values as we iterate, we can efficiently count all LIS.

Approach

The approach uses two arrays, len[n] and cnt[n], to store the length of the longest increasing subsequence ending at nums[i] and the count of such sequences, respectively.
- len[i]: Length of LIS ending at index i.
- cnt[i]: Number of LIS ending at index i.
For each index i:

Set len[i] = 1 and cnt[i] = 1 (every element is an LIS of length 1).
For each previous index j < i:
- If nums[i] > nums[j]:
- If len[j] + 1 > len[i], update len[i] = len[j] + 1 and set cnt[i] = cnt[j].
- If len[j] + 1 == len[i], increment cnt[i] by cnt[j].

Find the maximum value in len.
Sum all cnt[i] where len[i] equals the maximum length.

Code

 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


class Solution {
public:
   int findNumberOfLIS(vector<int>& nums) {
      int n = nums.size(), ans = 0, mx = 0;
      vector<int> len(n, 1), cnt(n, 1);
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
           if (nums[i] > nums[j]) {
              if (len[j] + 1 > len[i]) {
                len[i] = len[j] + 1;
                cnt[i] = cnt[j];
              } else if (len[j] + 1 == len[i]) {
                cnt[i] += cnt[j];
              }
           }
        }
        if (len[i] > mx) {
           mx = len[i];
           ans = cnt[i];
        } else if (len[i] == mx) {
           ans += cnt[i];
        }
      }
      return ans;
   }
};

 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


func findNumberOfLIS(nums []int) int {
   n := len(nums)
   lenArr := make([]int, n)
   cnt := make([]int, n)
   mx, ans := 0, 0
   for i := 0; i < n; i++ {
      lenArr[i], cnt[i] = 1, 1
      for j := 0; j < i; j++ {
        if nums[i] > nums[j] {
           if lenArr[j]+1 > lenArr[i] {
              lenArr[i] = lenArr[j] + 1
              cnt[i] = cnt[j]
           } else if lenArr[j]+1 == lenArr[i] {
              cnt[i] += cnt[j]
           }
        }
      }
      if lenArr[i] > mx {
        mx = lenArr[i]
        ans = cnt[i]
      } else if lenArr[i] == mx {
        ans += cnt[i]
      }
   }
   return ans
}

 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


class Solution {
   public int findNumberOfLIS(int[] nums) {
      int n = nums.length, ans = 0, mx = 0;
      int[] len = new int[n], cnt = new int[n];
      for (int i = 0; i < n; i++) {
        len[i] = cnt[i] = 1;
        for (int j = 0; j < i; j++) {
           if (nums[i] > nums[j]) {
              if (len[j] + 1 > len[i]) {
                len[i] = len[j] + 1;
                cnt[i] = cnt[j];
              } else if (len[j] + 1 == len[i]) {
                cnt[i] += cnt[j];
              }
           }
        }
        if (len[i] > mx) {
           mx = len[i];
           ans = cnt[i];
        } else if (len[i] == mx) {
           ans += cnt[i];
        }
      }
      return ans;
   }
}

 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


class Solution {
   fun findNumberOfLIS(nums: IntArray): Int {
      val n = nums.size
      val len = IntArray(n) { 1 }
      val cnt = IntArray(n) { 1 }
      var mx = 0
      var ans = 0
      for (i in 0 until n) {
        for (j in 0 until i) {
           if (nums[i] > nums[j]) {
              if (len[j] + 1 > len[i]) {
                len[i] = len[j] + 1
                cnt[i] = cnt[j]
              } else if (len[j] + 1 == len[i]) {
                cnt[i] += cnt[j]
              }
           }
        }
        if (len[i] > mx) {
           mx = len[i]
           ans = cnt[i]
        } else if (len[i] == mx) {
           ans += cnt[i]
        }
      }
      return ans
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
   def findNumberOfLIS(self, nums: list[int]) -> int:
      n = len(nums)
      if n == 0:
        return 0
      length = [1] * n
      count = [1] * n
      mx = 0
      ans = 0
      for i in range(n):
        for j in range(i):
           if nums[i] > nums[j]:
              if length[j] + 1 > length[i]:
                length[i] = length[j] + 1
                count[i] = count[j]
              elif length[j] + 1 == length[i]:
                count[i] += count[j]
        if length[i] > mx:
           mx = length[i]
           ans = count[i]
        elif length[i] == mx:
           ans += count[i]
      return ans

 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


impl Solution {
   pub fn find_number_of_lis(nums: Vec<i32>) -> i32 {
      let n = nums.len();
      if n == 0 { return 0; }
      let mut len = vec![1; n];
      let mut cnt = vec![1; n];
      let mut mx = 0;
      let mut ans = 0;
      for i in 0..n {
        for j in 0..i {
           if nums[i] > nums[j] {
              if len[j] + 1 > len[i] {
                len[i] = len[j] + 1;
                cnt[i] = cnt[j];
              } else if len[j] + 1 == len[i] {
                cnt[i] += cnt[j];
              }
           }
        }
        if len[i] > mx {
           mx = len[i];
           ans = cnt[i];
        } else if len[i] == mx {
           ans += cnt[i];
        }
      }
      ans
   }
}

Complexity

⏰ Time complexity: O(n^2), where n is the length of nums.
🧺 Space complexity: O(n) for the two arrays.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#