Sum of Good Subsequences

Problem Description

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. Return the sum of all possible good subsequences of nums. Since the answer may be very large, return it modulo 10^9 + 7. Note that a subsequence of size 1 is considered good by definition.

Key Insights

• A good subsequence can only include numbers that have an absolute difference of 1 between consecutive elements.
• Each unique element in nums can contribute to multiple good subsequences based on its neighboring values (i.e., num - 1 and num + 1).
• We can use a frequency map to count occurrences of each number to efficiently compute the sum of subsequences.

Space and Time Complexity

Time Complexity: O(n + k), where n is the length of nums and k is the range of numbers present (i.e., the maximum number in nums). Space Complexity: O(k), where k is the range of numbers present, for the frequency map.

Solution

To solve the problem, we can follow these steps:

1. Create a frequency map to count how many times each number appears in nums.
2. For each unique number in the frequency map, calculate the contribution of that number to good subsequences by considering its neighbors (i.e., number - 1 and number + 1).
3. Use dynamic programming to accumulate the contributions from each number and its neighbors.
4. Finally, return the total sum modulo 10^9 + 7.

Code Solutions