Longest increasing subsequence ii

Array Divide and Conquer Dynamic Programming Binary Indexed Tree Segment Tree Queue Monotonic Queue

26.1% acceptance

Feb 25, 2026

954

You are given an integer array nums and a positive integer k. Return the longest subsequence of nums that meets the following requirements: The subsequence is strictly increasing and The difference between adjacent elements in the subsequence is at most k. Note that a subsequence of an array is an array obtained by deleting some or no elements of the array without changing the relative order of the remaining elements.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn length_of_lis(nums: Vec<i32>, k: i32) -> i32 {
    let max_val = *nums.iter().max().unwrap() as usize;
    let mut seg = vec![0i32; (max_val + 1) * 4];

    fn update(seg: &mut Vec<i32>, node: usize, start: usize, end: usize, pos: usize, val: i32) {
      if start == end {
        seg[node] = seg[node].max(val);
        return;
      }
      let mid = (start + end) / 2;
      if pos <= mid {
        update(seg, node * 2, start, mid, pos, val);
      } else {
        update(seg, node * 2 + 1, mid + 1, end, pos, val);
      }
      seg[node] = seg[node * 2].max(seg[node * 2 + 1]);
    }

    fn query(seg: &[i32], node: usize, start: usize, end: usize, l: usize, r: usize) -> i32 {
      if r < start || end < l {
        return 0;
      }
      if l <= start && end <= r {
        return seg[node];
      }
      let mid = (start + end) / 2;
      query(seg, node * 2, start, mid, l, r).max(query(seg, node * 2 + 1, mid + 1, end, l, r))
    }

    let n = max_val;
    let mut ans = 1;
    for &num in &nums {
      let v = num as usize;
      let l = if v as i64 - k as i64 - 1 < 0 { 0 } else { (v as i64 - k as i64) as usize };
      let prev_max = if v == 0 { 0 } else { query(&seg, 1, 0, n, l, v - 1) };
      let new_len = prev_max + 1;
      ans = ans.max(new_len);
      update(&mut seg, 1, 0, n, v, new_len);
    }
    ans
  }
}