Sum of consecutive subsequences

Array Hash Table Dynamic Programming

43.4% acceptance

Mar 31, 2026

We call an array arr of length n consecutive if one of the following holds: arr[i] - arr[i - 1] == 1 for all 1 <= i < n. arr[i] - arr[i - 1] == -1 for all 1 <= i < n. The value of an array is the sum of its elements. For example, [3, 4, 5] is a consecutive array of value 12 and [9, 8] is another of value 17. While [3, 4, 3] and [8, 6] are not consecutive. Given an array of integers nums, return the sum of the values of all consecutive non-empty subsequences. Since the answer may be very large, return it modulo 109 + 7. Note that an array of length 1 is also considered consecutive.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn get_sum(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;

    let mut f_inc: HashMap<i32, i64> = HashMap::new();
    let mut g_inc: HashMap<i32, i64> = HashMap::new();
    let mut f_dec: HashMap<i32, i64> = HashMap::new();
    let mut g_dec: HashMap<i32, i64> = HashMap::new();

    let mut total: i64 = 0;
    let mut sum_nums: i64 = 0;

    for &v in &nums {
      let vl = v as i64;
      sum_nums = (sum_nums + vl) % MOD;

      // Increasing consecutive subsequences
      let fi = *f_inc.get(&(v - 1)).unwrap_or(&0);
      let gi = *g_inc.get(&(v - 1)).unwrap_or(&0);
      let new_count_inc = (1 + fi) % MOD;
      let new_sum_inc = (vl % MOD * new_count_inc % MOD + gi) % MOD;
      *f_inc.entry(v).or_insert(0) = (*f_inc.get(&v).unwrap_or(&0) + new_count_inc) % MOD;
      *g_inc.entry(v).or_insert(0) = (*g_inc.get(&v).unwrap_or(&0) + new_sum_inc) % MOD;
      total = (total + new_sum_inc) % MOD;

      // Decreasing consecutive subsequences
      let fd = *f_dec.get(&(v + 1)).unwrap_or(&0);
      let gd = *g_dec.get(&(v + 1)).unwrap_or(&0);
      let new_count_dec = (1 + fd) % MOD;
      let new_sum_dec = (vl % MOD * new_count_dec % MOD + gd) % MOD;
      *f_dec.entry(v).or_insert(0) = (*f_dec.get(&v).unwrap_or(&0) + new_count_dec) % MOD;
      *g_dec.entry(v).or_insert(0) = (*g_dec.get(&v).unwrap_or(&0) + new_sum_dec) % MOD;
      total = (total + new_sum_dec) % MOD;
    }

    // Subtract single elements (counted in both inc and dec)
    total = (total - sum_nums + MOD) % MOD;

    total as i32
  }
}