3299. Sum of Consecutive Subsequences

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.

class Solution {
    long long mod = 1e9 + 7;
    long long helper(vector<int>& nums, int op) {
        unordered_map<long long, pair<long long, long long>> dp;
        long long res = 0;
        for(auto& n : nums) {
            long long sum = 0, cnt = 1;
            if(dp.count(n + op)) {
                sum = (sum + dp[n + op].first) % mod;
                cnt = (cnt + dp[n + op].second) % mod;
            }
            sum = (sum + cnt * n % mod) % mod;
            dp[n].first = (dp[n].first + sum) % mod;
            dp[n].second = (dp[n].second + cnt) % mod;
        }
        for(auto& [_,p] : dp) res = (res + p.first) % mod;
        return res;
    }
public:
    int getSum(vector<int>& nums) {
        return (helper(nums, 1) + helper(nums, -1) - accumulate(begin(nums), end(nums), 0ll) % mod + mod) % mod;
    }
};