Longest subsequence with decreasing adjacent difference

Array Dynamic Programming

16.6% acceptance

Feb 25, 2026

150

You are given an array of integers nums. Your task is to find the length of the longest subsequence seq of nums, such that the absolute differences between consecutive elements form a non-increasing sequence of integers. In other words, for a subsequence seq0, seq1, seq2, ..., seqm of nums, |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1|. Return the length of such a subsequence.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subsequence(nums: Vec<i32>) -> i32 {
    let max_val = 300usize;
    // val_dp[v][d] = best suffix-max length for subsequences ending at a position with value v,
    // where last diff >= d
    let mut val_dp = vec![vec![0i32; max_val + 2]; max_val + 1];
    let mut ans = 1i32;

    for &num in &nums {
      let v = num as usize;
      let mut dp = vec![0i32; max_val + 2];

      for u in 1..=max_val {
        let d_new = if v >= u { v - u } else { u - v };
        if d_new <= max_val && val_dp[u][d_new] > 0 {
          if val_dp[u][d_new] + 1 > dp[d_new] {
            dp[d_new] = val_dp[u][d_new] + 1;
          }
        }
      }

      // Compute suffix max (from high diff down to 0), baseline = 1 (single element)
      let mut cur_suf = vec![0i32; max_val + 2];
      cur_suf[max_val] = dp[max_val].max(1);
      for d in (0..max_val).rev() {
        cur_suf[d] = cur_suf[d + 1].max(dp[d]).max(1);
      }

      ans = ans.max(cur_suf[0]);

      // Update val_dp for value v
      for d in 0..=max_val {
        if cur_suf[d] > val_dp[v][d] {
          val_dp[v][d] = cur_suf[d];
        }
      }
    }

    ans
  }
}