Sum of Good Subsequences - Video Solutions

Problem Overview: You are given an integer array and need the total sum of all good subsequences. A subsequence is considered good when the absolute difference between every pair of adjacent elements equals 1. Instead of listing subsequences explicitly, the goal is to efficiently accumulate the sum contributed by every valid subsequence.

Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)

Generate every subsequence using recursion or bitmasking. For each subsequence, check whether the absolute difference between adjacent elements equals 1. If the subsequence is valid, compute its element sum and add it to the global result. This approach directly follows the definition but quickly becomes impractical because the number of subsequences grows exponentially. It only works for very small arrays and mainly serves as a conceptual baseline.

Approach 2: Dynamic Programming with Hash Map (O(n) time, O(n) space)

The key observation: a good subsequence ending with value x can only extend from subsequences ending with x-1 or x+1. Maintain two hash maps: count[v] for the number of good subsequences ending with value v, and sum[v] for the total sum of all such subsequences. When processing a new element v, create new subsequences in three ways: the single-element subsequence [v], extensions of subsequences ending in v-1, and extensions of those ending in v+1.

When extending a subsequence ending at k, the new sum increases by v. So the contribution from that side becomes sum[k] + count[k] * v. Add contributions from both neighbors and update the maps for value v. Accumulate the newly created sums into the final answer. A hash map ensures constant-time lookups for v-1 and v+1, making the algorithm linear with respect to the array length.

This approach relies on incremental aggregation instead of explicitly building subsequences. Each number only interacts with two neighboring states, which keeps the transitions simple and efficient.

Recommended for interviews: Interviewers expect the dynamic programming solution combined with a hash table. The brute force method demonstrates understanding of subsequences but fails on constraints. The DP transition using neighbor values shows strong reasoning about state compression and works efficiently with arrays of large size.