Sum of good subsequences

Array Hash Table Dynamic Programming

30.8% acceptance

Feb 24, 2026

157

You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1. Return the sum of all possible good subsequences of nums. Since the answer may be very large, return it modulo 109 + 7. Note that a subsequence of size 1 is considered good by definition.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn sum_of_good_subsequences(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // dp_sum[v] = sum of all good subseqs ending with v
    // dp_cnt[v] = count of all good subseqs ending with v
    // For each nums[i] = v:
    //   new_cnt[v] += 1 (singleton) + dp_cnt[v-1] + dp_cnt[v+1]
    //   new_sum[v] += v (singleton) + dp_sum[v-1] + (dp_cnt[v-1] * v) + dp_sum[v+1] + (dp_cnt[v+1] * v)
    let mut dp_sum: HashMap<i32, i64> = HashMap::new();
    let mut dp_cnt: HashMap<i32, i64> = HashMap::new();
    
    for &v in &nums {
      let cnt_prev = *dp_cnt.get(&(v - 1)).unwrap_or(&0);
      let cnt_next = *dp_cnt.get(&(v + 1)).unwrap_or(&0);
      let sum_prev = *dp_sum.get(&(v - 1)).unwrap_or(&0);
      let sum_next = *dp_sum.get(&(v + 1)).unwrap_or(&0);
      
      let add_cnt = (1 + cnt_prev + cnt_next) % MOD;
      let add_sum = (v as i64 + sum_prev + cnt_prev * v as i64 % MOD + sum_next + cnt_next * v as i64 % MOD) % MOD;
      
      *dp_cnt.entry(v).or_insert(0) = (*dp_cnt.entry(v).or_insert(0) + add_cnt) % MOD;
      *dp_sum.entry(v).or_insert(0) = (*dp_sum.entry(v).or_insert(0) + add_sum) % MOD;
    }
    
    (dp_sum.values().sum::<i64>() % MOD) as i32
  }
}