# Sum of Good Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/sum-of-good-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-good-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
---
## Problem
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** `109 + 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 <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute-Force Backtracking
The most straightforward, yet inefficient, way to solve this problem is to generate all possible subsequences of the input array `nums`. For each generated subsequence, we check if it meets the criteria of a 'good' subsequence. If it does, we calculate the sum of its elements and add it to a global total. This can be implemented using recursion or iteration to generate the power set of `nums`.
**Time:** O(2^N * N). There are 2^N possible subsequences. For each subsequence of length k, it takes O(k) to check if it's good and to sum its elements. In the worst case, this leads to an exponential time complexity. · **Space:** O(N), where N is the length of `nums`. This space is used by the recursion call stack. The depth of the recursion can go up to N.
**Pros:** Conceptually simple and easy to understand.; A direct translation of the problem statement into code.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.; Generates and checks many subsequences that are not 'good', leading to wasted computation.
### Explanation
This approach uses a classic backtracking algorithm to explore every possible subsequence. We can define a recursive function that builds a subsequence element by element. At each step, we decide whether to include the current element from the `nums` array into the subsequence we are building.

When we consider including an element, we must first verify that it preserves the 'good' subsequence property. A number can be appended to the current subsequence only if the subsequence is empty or if the absolute difference between the number and the last element of the subsequence is exactly 1. If the condition is met, we add the number, add the new subsequence's sum to our total answer, and recurse further. If not, we backtrack and explore other possibilities.

While this correctly finds all good subsequences, its performance is very poor. The total number of subsequences is 2^N, where N is the length of `nums`. For each subsequence, we perform a check and a sum, leading to a time complexity that is exponential, making it infeasible for the problem's constraints.
### Algorithm
*   Define a recursive function, say `solve(index, currentSubsequence)`.
*   The base case for the recursion is when `index` reaches the end of the `nums` array.
*   In the recursive step, for each element `nums[index]`, we have two choices:
    1.  **Exclude `nums[index]`**: Recursively call `solve(index + 1, currentSubsequence)`.
    2.  **Include `nums[index]`**: Check if adding `nums[index]` to `currentSubsequence` maintains the 'good' property. This is true if `currentSubsequence` is empty or `abs(nums[index] - last_element_of_subsequence) == 1`.
*   If it's valid to include `nums[index]`, form a new subsequence, add its sum to a running total, and make a recursive call `solve(index + 1, newSubsequence)`.
*   This method explores all 2^N subsequences, checks each for the 'good' property, and sums them up if they are.

## Dynamic Programming on Index
A better approach involves dynamic programming. We can build the solution based on subproblems. Let `dp[i]` be the sum of all good subsequences that end with the element at index `i`. To compute `dp[i]`, we can iterate through all previous elements `nums[j]` (where `j < i`) and, if `nums[i]` can extend a good subsequence ending at `nums[j]`, we add the contribution to `dp[i]`. We also need to keep track of the count of such subsequences.
**Time:** O(N^2) due to the nested loops required to check every previous element for each element in `nums`. · **Space:** O(N) to store the `dp` and `count` arrays.
**Pros:** Significant improvement over the brute-force approach.; Correctly utilizes the overlapping subproblems property of dynamic programming.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), and will time out.
### Explanation
This method uses dynamic programming based on the indices of the array. We create two arrays, `dp` and `count`, of the same size as `nums`.

- `dp[i]`: Stores the cumulative sum of all good subsequences that end with the element `nums[i]`.
- `count[i]`: Stores the total number of good subsequences that end with `nums[i]`.

We iterate from `i = 0` to `n-1`. For each element `nums[i]`, we first consider it as a subsequence of length one. So, we initialize `dp[i] = nums[i]` and `count[i] = 1`. Then, we iterate through all previous elements `nums[j]` where `j < i`. If `abs(nums[i] - nums[j]) == 1`, it means we can append `nums[i]` to any good subsequence that ended at `j`. The sum of these new subsequences is the sum of the old subsequences (`dp[j]`) plus `nums[i]` added for each old subsequence (`count[j] * nums[i]`). We add this to `dp[i]` and update `count[i]` by adding `count[j]`. The final answer is the sum of all `dp[i]` values.

```java
class Solution {
    public int sumOfGoodSubsequences(int[] nums) {
        int n = nums.length;
        long MOD = 1_000_000_007;
        long[] dp = new long[n];
        long[] count = new long[n];
        long totalSum = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = nums[i];
            count[i] = 1;
            for (int j = 0; j < i; j++) {
                if (Math.abs(nums[i] - nums[j]) == 1) {
                    dp[i] = (dp[i] + dp[j] + (count[j] * nums[i])) % MOD;
                    count[i] = (count[i] + count[j]) % MOD;
                }
            }
            totalSum = (totalSum + dp[i]) % MOD;
        }
        return (int) totalSum;
    }
}
```
### Algorithm
*   Initialize two arrays, `dp` and `count`, of size `N` (the length of `nums`).
*   `dp[i]` will store the sum of all good subsequences ending with `nums[i]`.
*   `count[i]` will store the number of good subsequences ending with `nums[i]`.
*   Initialize a variable `totalSum = 0`.
*   Iterate through `nums` with an index `i` from `0` to `N-1`.
    *   For each `i`, initialize `dp[i] = nums[i]` and `count[i] = 1` to account for the subsequence `[nums[i]]`.
    *   Start an inner loop with index `j` from `0` to `i-1`.
        *   If `abs(nums[i] - nums[j]) == 1`, it means we can extend the good subsequences ending at `j`.
        *   Update `dp[i]` by adding the sum of these newly formed subsequences: `dp[i] += dp[j] + count[j] * nums[i]`.
        *   Update `count[i]` by adding the count of subsequences from `j`: `count[i] += count[j]`.
    *   After the inner loop, add `dp[i]` to `totalSum`.
*   Return `totalSum` modulo 10^9 + 7.

## Optimized Dynamic Programming on Value
The O(N^2) DP approach can be optimized to O(N). The inner loop in the previous approach is inefficient because it re-scans all previous elements. We can observe that to compute the state for a number `num`, we only need the aggregated information for numbers `num-1` and `num+1`. We can maintain this information in an array or a hash map, where the key is the number's value, allowing for O(1) lookups.
**Time:** O(N), where N is the length of `nums`. We iterate through the array once, and all operations inside the loop are constant time. · **Space:** O(M), where M is the maximum value in `nums`. This is for the DP arrays. Given `M <= 10^5`, this is efficient.
**Pros:** Optimal time complexity, making it very efficient for the given constraints.; Single pass through the input array.
**Cons:** Requires extra space proportional to the range of values in the input array, which could be large if the values are not bounded.
### Explanation
This optimal approach uses dynamic programming where the state is based on the *value* of the elements, not their indices. We use two arrays, `sumEndingWith` and `countEndingWith`, to store the running totals.

- `sumEndingWith[v]`: The sum of all good subsequences encountered so far that end with the value `v`.
- `countEndingWith[v]`: The count of all good subsequences encountered so far that end with the value `v`.

We iterate through `nums` once. For each number `num`, we calculate the sum and count of new good subsequences that end with this specific `num`. These can be formed in three ways:
1.  A new subsequence of size one: `[num]`. Its sum is `num` and count is 1.
2.  By extending all existing good subsequences that end with `num - 1`.
3.  By extending all existing good subsequences that end with `num + 1`.

The total sum for subsequences ending at the current `num` is the sum of contributions from these three sources. We can get the required information for `num-1` and `num+1` directly from our DP arrays in O(1) time. After calculating the sum (`currentSum`) for the current `num`, we add it to our overall `totalSum` and update the DP arrays `sumEndingWith[num]` and `countEndingWith[num]` for future elements to use.

Since `nums[i]` is bounded by 10^5, arrays are a suitable choice for storing the DP states.

```java
class Solution {
    public int sumOfGoodSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        // We need to access num+1, so size should be maxVal + 2
        long[] sumEndingWith = new long[maxVal + 2];
        long[] countEndingWith = new long[maxVal + 2];
        long totalSum = 0;

        for (int num : nums) {
            long sumPrevMinus1 = (num > 0) ? sumEndingWith[num - 1] : 0;
            long countPrevMinus1 = (num > 0) ? countEndingWith[num - 1] : 0;
            
            long sumPrevPlus1 = sumEndingWith[num + 1];
            long countPrevPlus1 = countEndingWith[num + 1];

            long term1 = (countPrevMinus1 * num) % MOD;
            long term2 = (countPrevPlus1 * num) % MOD;

            long currentSum = (num + sumPrevMinus1 + term1 + sumPrevPlus1 + term2) % MOD;
            long currentCount = (1 + countPrevMinus1 + countPrevPlus1) % MOD;

            totalSum = (totalSum + currentSum) % MOD;

            sumEndingWith[num] = (sumEndingWith[num] + currentSum) % MOD;
            countEndingWith[num] = (countEndingWith[num] + currentCount) % MOD;
        }

        return (int) totalSum;
    }
}
```
### Algorithm
*   Initialize two arrays (or hash maps), `sumEndingWith` and `countEndingWith`, to store the DP states. The size should be based on the maximum possible value in `nums`.
*   Initialize `totalSum = 0` and `MOD = 10^9 + 7`.
*   Iterate through each `num` in the input array `nums`.
    *   For the current `num`, retrieve the total sum and count of good subsequences ending in `num - 1` and `num + 1` from the DP arrays.
    *   Calculate `currentSum`, the sum of all good subsequences ending with the *current* `num`. This is `num` (for the subsequence `[num]`) plus the sums from extending subsequences ending in `num-1` and `num+1`.
    *   The formula is: `currentSum = (num + sumEndingWith[num-1] + countEndingWith[num-1] * num + sumEndingWith[num+1] + countEndingWith[num+1] * num) % MOD`.
    *   Calculate `currentCount`, the number of such subsequences: `currentCount = (1 + countEndingWith[num-1] + countEndingWith[num+1]) % MOD`.
    *   Add `currentSum` to the `totalSum`.
    *   Update the DP state for value `num`: `sumEndingWith[num] += currentSum` and `countEndingWith[num] += currentCount`.
*   Return the final `totalSum`.

# Solutions
### Java

```java
class Solution {
public
  int sumOfGoodSubsequences(int[] nums) {
    final int mod = (int)1 e9 + 7;
    int mx = 0;
    for (int x : nums) {
      mx = Math.max(mx, x);
    }
    long[] f = new long[mx + 1];
    long[] g = new long[mx + 1];
    for (int x : nums) {
      f[x] += x;
      g[x] += 1;
      if (x > 0) {
        f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;
        g[x] = (g[x] + g[x - 1]) % mod;
      }
      if (x + 1 <= mx) {
        f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;
        g[x] = (g[x] + g[x + 1]) % mod;
      }
    }
    long ans = 0;
    for (long x : f) {
      ans = (ans + x) % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOfGoodSubsequences(vector<int> &nums) {
    const int mod = 1e9 + 7;
    int mx = ranges ::max(nums);
    vector<long long> f(mx + 1), g(mx + 1);
    for (int x : nums) {
      f[x] += x;
      g[x] += 1;
      if (x > 0) {
        f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;
        g[x] = (g[x] + g[x - 1]) % mod;
      }
      if (x + 1 <= mx) {
        f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;
        g[x] = (g[x] + g[x + 1]) % mod;
      }
    }
    return accumulate(f.begin(), f.end(), 0LL) % mod;
  }
};

```

### Python

```python
class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 f = defaultdict(int) g = defaultdict(int) for x in nums: f[x] += x g[x] += 1 f[x] += f[x - 1] + g[x - 1] * x g[x] += g[x - 1] f[x] += f[x + 1] + g[x + 1] * x g[x] += g[x + 1] return sum(f . values()) % mod

```