Watch 10 video solutions for Sum of Good Subsequences, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by Greg Hogg has 367,081 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[1], [2], [1], [1,2], [2,1], [1,2,1].Example 2:
Input: nums = [3,4,5]
Output: 40
Explanation:
[3], [4], [5], [3,4], [4,5], [3,4,5].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105