Sum of consecutive subarrays

Array Two Pointers Dynamic Programming

42.7% 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 subarrays. 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(1)

LeetCode

solution.rs

impl Solution {
  pub fn get_sum(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let nums: Vec<i64> = nums.into_iter().map(|x| x as i64).collect();

    let mut total: i64 = 0;

    // Increasing consecutive subarrays
    let mut run_inc: i64 = 1;
    let mut dp_inc: i64 = nums[0] % MOD;
    total = (total + dp_inc) % MOD;

    for i in 1..n {
      if nums[i] == nums[i - 1] + 1 {
        run_inc += 1;
        dp_inc = (dp_inc + run_inc % MOD * (nums[i] % MOD) % MOD) % MOD;
      } else {
        run_inc = 1;
        dp_inc = nums[i] % MOD;
      }
      total = (total + dp_inc) % MOD;
    }

    // Decreasing consecutive subarrays
    let mut run_dec: i64 = 1;
    let mut dp_dec: i64 = nums[0] % MOD;
    total = (total + dp_dec) % MOD;

    for i in 1..n {
      if nums[i] == nums[i - 1] - 1 {
        run_dec += 1;
        dp_dec = (dp_dec + run_dec % MOD * (nums[i] % MOD) % MOD) % MOD;
      } else {
        run_dec = 1;
        dp_dec = nums[i] % MOD;
      }
      total = (total + dp_dec) % MOD;
    }

    // Subtract single elements (counted in both inc and dec)
    let sum_nums: i64 = nums.iter().sum::<i64>() % MOD;
    total = (total - sum_nums % MOD + MOD) % MOD;

    total as i32
  }
}