Number of longest increasing subsequence

Array Dynamic Programming Binary Indexed Tree Segment Tree

51.4% acceptance

Feb 20, 2026

7285

288

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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![1i32; n];
    let mut cnt = vec![1i32; n];
    for i in 1..n {
      for j in 0..i {
        if nums[j] < nums[i] {
          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];
          }
        }
      }
    }
    let max_len = *len.iter().max().unwrap();
    len.iter().zip(cnt.iter())
      .filter(|&(&l, _)| l == max_len)
      .map(|(_, &c)| c)
      .sum()
  }
}