Problem

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.

Examples

Example 1:

1
2
3
4

Input: nums = [1,2]
Output: 6
Explanation:
The consecutive subsequences are: `[1]`, `[2]`, `[1, 2]`.

Example 2:

1
2
3
4
5

Input: nums = [1,4,2,3]
Output: 31
Explanation:
The consecutive subsequences are: `[1]`, `[4]`, `[2]`, `[3]`, `[1, 2]`, `[2,
3]`, `[4, 3]`, `[1, 2, 3]`.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Dynamic Programming with Hash Maps

Intuition

For each number, keep track of the sum and count of consecutive subsequences ending at that number for both increasing and decreasing directions. For each number, extend all subsequences ending at num-1 (for increasing) and num+1 (for decreasing), and also start a new subsequence with the current number.

Approach

  1. Use two hash maps: one for increasing (inc) and one for decreasing (dec) subsequences. Each stores (sum, count) for subsequences ending at a value.
  2. For each number in nums:
    • For increasing: get (sum, count) for num-1, update for num.
    • For decreasing: get (sum, count) for num+1, update for num.
    • Add the current number as a new subsequence.
    • Add all contributions to the answer.
  3. Return the answer modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <unordered_map>
class Solution {
public:
    int sumOfConsecutiveSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        unordered_map<int, pair<long long, long long>> inc, dec;
        long long ans = 0;
        for (int x : nums) {
            auto [inc_sum, inc_cnt] = inc[x-1];
            auto [dec_sum, dec_cnt] = dec[x+1];
            long long new_inc_sum = (inc_sum + inc_cnt * x) % mod;
            long long new_dec_sum = (dec_sum + dec_cnt * x) % mod;
            inc[x].first = (new_inc_sum + x) % mod;
            inc[x].second = (inc_cnt + 1) % mod;
            dec[x].first = (new_dec_sum + x) % mod;
            dec[x].second = (dec_cnt + 1) % mod;
            ans = (ans + inc[x].first + dec[x].first - x + mod) % mod;
        }
        return (int)ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func sumOfConsecutiveSubsequences(nums []int) int {
    mod := int(1e9 + 7)
    inc := map[int][2]int64{}
    dec := map[int][2]int64{}
    var ans int64
    for _, x := range nums {
        incSum, incCnt := inc[x-1][0], inc[x-1][1]
        decSum, decCnt := dec[x+1][0], dec[x+1][1]
        newIncSum := (incSum + incCnt*int64(x)) % int64(mod)
        newDecSum := (decSum + decCnt*int64(x)) % int64(mod)
        inc[x] = [(newIncSum + int64(x)) % int64(mod), (incCnt + 1) % int64(mod)]
        dec[x] = [(newDecSum + int64(x)) % int64(mod), (decCnt + 1) % int64(mod)]
        ans = (ans + inc[x][0] + dec[x][0] - int64(x) + int64(mod)) % int64(mod)
    }
    return int(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int sumOfConsecutiveSubsequences(int[] nums) {
        int mod = 1_000_000_007;
        Map<Integer, long[]> inc = new HashMap<>();
        Map<Integer, long[]> dec = new HashMap<>();
        long ans = 0;
        for (int x : nums) {
            long[] incPrev = inc.getOrDefault(x-1, new long[2]);
            long[] decPrev = dec.getOrDefault(x+1, new long[2]);
            long newIncSum = (incPrev[0] + incPrev[1] * x) % mod;
            long newDecSum = (decPrev[0] + decPrev[1] * x) % mod;
            inc.put(x, new long[]{(newIncSum + x) % mod, (incPrev[1] + 1) % mod});
            dec.put(x, new long[]{(newDecSum + x) % mod, (decPrev[1] + 1) % mod});
            ans = (ans + inc.get(x)[0] + dec.get(x)[0] - x + mod) % mod;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun sumOfConsecutiveSubsequences(nums: IntArray): Int {
        val mod = 1_000_000_007L
        val inc = mutableMapOf<Int, Pair<Long, Long>>()
        val dec = mutableMapOf<Int, Pair<Long, Long>>()
        var ans = 0L
        for (x in nums) {
            val (incSum, incCnt) = inc.getOrDefault(x-1, 0L to 0L)
            val (decSum, decCnt) = dec.getOrDefault(x+1, 0L to 0L)
            val newIncSum = (incSum + incCnt * x) % mod
            val newDecSum = (decSum + decCnt * x) % mod
            inc[x] = ((newIncSum + x) % mod) to ((incCnt + 1) % mod)
            dec[x] = ((newDecSum + x) % mod) to ((decCnt + 1) % mod)
            ans = (ans + inc[x]!!.first + dec[x]!!.first - x + mod) % mod
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def sumOfConsecutiveSubsequences(self, nums: list[int]) -> int:
        mod = 10 ** 9 + 7
        inc: dict[int, tuple[int, int]] = {}
        dec: dict[int, tuple[int, int]] = {}
        ans = 0
        for x in nums:
            inc_sum, inc_cnt = inc.get(x-1, (0, 0))
            dec_sum, dec_cnt = dec.get(x+1, (0, 0))
            new_inc_sum = (inc_sum + inc_cnt * x) % mod
            new_dec_sum = (dec_sum + dec_cnt * x) % mod
            inc[x] = ((new_inc_sum + x) % mod, (inc_cnt + 1) % mod)
            dec[x] = ((new_dec_sum + x) % mod, (dec_cnt + 1) % mod)
            ans = (ans + inc[x][0] + dec[x][0] - x + mod) % mod
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::HashMap;
impl Solution {
    pub fn sum_of_consecutive_subsequences(nums: Vec<i32>) -> i32 {
        let modn = 1_000_000_007i64;
        let mut inc: HashMap<i32, (i64, i64)> = HashMap::new();
        let mut dec: HashMap<i32, (i64, i64)> = HashMap::new();
        let mut ans = 0i64;
        for &x in &nums {
            let (inc_sum, inc_cnt) = *inc.get(&(x-1)).unwrap_or(&(0,0));
            let (dec_sum, dec_cnt) = *dec.get(&(x+1)).unwrap_or(&(0,0));
            let new_inc_sum = (inc_sum + inc_cnt * x as i64) % modn;
            let new_dec_sum = (dec_sum + dec_cnt * x as i64) % modn;
            inc.insert(x, ((new_inc_sum + x as i64) % modn, (inc_cnt + 1) % modn));
            dec.insert(x, ((new_dec_sum + x as i64) % modn, (dec_cnt + 1) % modn));
            let (inc_sum2, _) = inc[&x];
            let (dec_sum2, _) = dec[&x];
            ans = (ans + inc_sum2 + dec_sum2 - x as i64 + modn) % modn;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    sumOfConsecutiveSubsequences(nums: number[]): number {
        const mod = 1e9 + 7;
        const inc = new Map<number, [number, number]>();
        const dec = new Map<number, [number, number]>();
        let ans = 0;
        for (const x of nums) {
            const [incSum, incCnt] = inc.get(x-1) ?? [0, 0];
            const [decSum, decCnt] = dec.get(x+1) ?? [0, 0];
            const newIncSum = (incSum + incCnt * x) % mod;
            const newDecSum = (decSum + decCnt * x) % mod;
            inc.set(x, [(newIncSum + x) % mod, (incCnt + 1) % mod]);
            dec.set(x, [(newDecSum + x) % mod, (decCnt + 1) % mod]);
            ans = (ans + inc.get(x)![0] + dec.get(x)![0] - x + mod) % mod;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each number is processed in constant time with hash map lookups and updates.
  • 🧺 Space complexity: O(n) — For storing hash maps for increasing and decreasing subsequences.