Sum of Good Subsequences

Sum of Good Subsequences

What is this problem about?

In this problem, a "good subsequence" is defined as a subsequence where the absolute difference between any two consecutive elements is exactly 1. You are given an array of integers and need to find the sum of the elements of all possible "good subsequences." Since the result can be very large, return it modulo $10^9 + 7$. Note that identical subsequences starting at different indices are counted separately.

Why is this asked in interviews?

Google asks this Hard-level problem to test a candidate's proficiency in Dynamic Programming and combinatorics. It's not enough to count the subsequences; you must also track the sum of their elements. This requires maintaining two DP states simultaneously (count and sum), making it a great test of logical structuring.

Algorithmic pattern used

The pattern is "Dynamic Programming with Frequency Hashing." We use two maps or arrays:

• count[x]: Number of good subsequences ending with value x.
• total_sum[x]: The sum of all elements of all good subsequences ending with value x. As we iterate through the array and see a value v, it can extend any good subsequence ending in v-1 or v+1.
• count[v] = count[v] + count[v-1] + count[v+1] + 1 (the +1 is for the subsequence starting and ending at v).
• total_sum[v] is updated by adding the sums of existing subsequences and the contribution of the new element v.

Example explanation

Array: [1, 2, 1]

• Process 1: count[1] = 1, total_sum[1] = 1.
• Process 2: count[2] = count[1] + 1 = 2. total_sum[2] = (total_sum[1] + 2*count[1]) + 2 = (1 + 2) + 2 = 5. (Subsequences: [2], [1, 2])
• Process 3 (another 1): count[1] = count[1] + count[2] + 1 = 1 + 2 + 1 = 4. total_sum[1] is updated similarly. The total result is the sum of total_sum[x] for all x.

Common mistakes candidates make

1. Exponential Solution: Attempting to generate all subsequences.
2. Incorrect Sum Update: Forgetting that each existing subsequence of count C adds the new value v exactly C times to the total sum.
3. Modulo errors: Not applying modulo at every step of the addition, leading to overflow before the final result.

Interview preparation tip

When a problem asks for the "sum of elements" across many combinations, try to track both the "number of ways" and the "running sum" in your DP. This is a very common pattern in counting problems.