3646. Sum Of Good Subsequences¶

3646. Sum of Good Subsequences

Hard

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.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Return the sum of all possible good subsequences of nums.

Since the answer may be very large, return it modulo 10⁹ + 7.

Note that a subsequence of size 1 is considered good by definition.

Example 1:

Input: nums = [1,2,1]

Output: 14

Explanation:

Good subsequences are: [1], [2], [1], [1,2], [2,1], [1,2,1].
The sum of elements in these subsequences is 14.

Example 2:

Input: nums = [3,4,5]

Output: 40

Explanation:

Good subsequences are: [3], [4], [5], [3,4], [4,5], [3,4,5].
The sum of elements in these subsequences is 40.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Solution¶

class Solution {
    private int mod = (int)(1e9 + 7);
    public int sumOfGoodSubsequences(int[] nums) {
        HashMap<Long, long[]> dp = new HashMap<>();
        long res = 0;
        for (long i : nums) {
            long sum = i, count = 1;
            if (dp.containsKey(i - 1)) {
                long[] temp = dp.get(i - 1);
                sum = (sum + temp[1] * i) % mod;
                sum = (sum + temp[0]) % mod;
                count = (count + temp[1]) % mod;
            }
            if (dp.containsKey(i + 1)) {
                long[] temp = dp.get(i + 1);
                sum = (sum + temp[1] * i) % mod;
                sum = (sum + temp[0]) % mod;
                count = (count + temp[1]) % mod;
            }
            res = (res + sum) % mod;
            long[] temp = dp.getOrDefault(i, new long[] {0, 0});
            temp[0] = (temp[0] + sum) % mod;
            temp[1] = (temp[1] + count) % mod;
            dp.put(i, temp);
        }
        return (int)res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]